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。
查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
完整代码：
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\n", dp[K][N]);
21. }
22. return 0;
23.}
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索each
， bar
， symbol
， of
， The
Codes
uva wine bar、bar codes talk、bar codes、bar339dp、10721，以便于您获取更多的相关知识。