2013-07-31 19:55:34Morris
[UVA][dp] 986 - How Many
Universidade da Beira Interior 21-10-2006
Problem H
How Many?
Let us consider paths in the plane integer lattice Z × Z consisting only of steps (1,1) and (1,−1) and which never pass below the x-axis. A peak at height k is then defined as a point on the path with coordinate y=k that is immediately preceded by a (1,1) step and immediately followed by a (1,−1) step. The pictures below show two such paths: on the left picture we have 4 peaks (2 peaks at height 2 and 2 peaks at height 3); while on the right picture we have 3 peaks (1 peak at height 1, 1 peak at height 2 and 1 peak at height 3).
Problem
The problem consists of counting the number of admissible paths starting at (0,0) and ending at (2n,0) with exactly r peaks at height k.Input
The input file contains several test cases, each of them consists of one line with the natural numbers n, r and k which define the problem (first number gives n, second number r, and the last one k). Assume that 1 ≤ n < 20, 0 ≤ r < 20, and 1 ≤ k < 20.Output
For each test case, the output is a single integer on a line by itself, answering the problem, being guaranteed to be less than 231.Sample Input
3 1 2 10 3 2
Sample Output
2 2002
Maratona Inter-Universitária de Programação 2006 MIUP'2006
Author: Delfim Torres (Universidade de Aveiro)
題目描述：
找到長度為 2*n 且存在恰好 k 個高度為 r 的山峰，也是有可能會存在比 r 高或低的山峰。
題目解法：
假設一個 dp[i][j][k] 表示當前使用的長度，以及最後停留的位置且已經存在 k 個高度為 R 的山峰。
考慮每一次增加一個隨機高度的山峰，而且增加的時候一定是補上 /\，但於由於要銜接最後停留的高度，
因此會多接幾個 / 來增加高度，直到指定高度。而一定要補上 \，或者多個 \，以確保這個山峰成立。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[55][105][55];// len, last height, ? peak at height k
int main() {
int N, R, K;
int i, j, k, p, q, r;
while(scanf("%d %d %d", &N, &R, &K) == 3) {
memset(dp, 0, sizeof(dp));
dp[0][0][0] = 1;
for(i = 0; i <= 2*N; i++) {//len
for(j = 0; j <= N; j++) {//last height
for(k = 0; k <= R; k++) {// ? peak at height K
if(dp[i][j][k] == 0)
continue;
for(p = j+1; p <= N; p++) {//next peak
int ext = p-j, tk = (p == K);
if(tk+k > R) continue;
for(q = p-1; q >= 0; q--) {//last height
if(i+ext+p-q > 2*N) break;
dp[i+ext+p-q][q][k+tk] += dp[i][j][k];
}
}
}
}
}
printf("%d\n", dp[2*N][0][R]);
}
return 0;
}