UVa 10721 Bar Codes （DP）

UVa 10721 Bar Codes （DP）2014-07-08 synapse7

10721 - Bar Codes

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1662

A bar-code symbol consists of alternating dark and light bars, starting with a dark bar on the left. Each bar is a number of units wide. Figure 1 shows a bar-code symbol consisting of 4 bars that extend over 1+2+3+1=7 units.

Figure 1: Bar-code over 7 units with 4 bars

In general, the bar code BC（n,k,m） is the set of all symbols with k bars that together extend over exactly n units, each bar being at most m units wide. For instance, the symbol in Figure 1 belongs to BC（7,4,3） but not to BC（7,4,2）. Figure 2 shows all 16 symbols in BC（7,4,3）. Each `1" represents a dark unit, each `0" a light unit.

0: 1000100 | 4: 1001110 | 8: 1100100 | 12: 1101110

1: 1000110 | 5: 1011000 | 9: 1100110 | 13: 1110010

2: 1001000 | 6: 1011100 | 10: 1101000 | 14: 1110100

3: 1001100 | 7: 1100010 | 11: 1101100 | 15: 1110110

Figure 2: All symbols of BC（7,4,3）

Input

Each input will contain three positive integers n, k, and m （1 ≤ n, k, m≤ 50）.

Output

For each input print the total number of symbols in BC（n,k,m）. Output will fit in 64-bit signed integer.

思路：我们可以设dp[i][j]表示有i个bar，j个unit的情况数，那么dp[i][j]=sum{dp[i-1][j-k]},1<=k<=M。

完整代码：

01./*0.016s*/02.03.#include<cstdio>04.#include<cstring>05.const int MAXD = 55;06.07.long long dp[MAXD][MAXD];08.09.int main（）10.{11.int N, K, M, i, j, k;12.while （~scanf（"%d%d%d", &N, &K, &M））13.{14.memset（dp, 0, sizeof（dp））;15.for （i = 1; i <= M && i <= N; ++i） dp[1][i] = 1;///仅有一个相邻块的情况肯定只有一种16.for （i = 2; i <= K; ++i）17.for （j = i; j <= N; ++j）18.for （k = 1; k < j && k <= M; ++k）19.dp[i][j] += dp[i - 1][j - k];20.printf（"%lld
", dp[K][N]）;21.}22.return 0;23.}