[UVA][dp] 10721 - Bar Codes
Problem D |
Bar Codes |
Time Limit |
1 Second |
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.
Sample Input |
Output for Sample Input |
7 4 3 |
16 |
要求要長度為 N 分成 K 團，每團最多 M 個。
遞迴公式思路：
依序放入第 i 團，記錄當前長度為 j，試圖放入新的團(size <= M)。
dp[i][j] = sigma( dp[i-1][j-size]);
#include <stdio.h>
#include <string.h>
long long dp[55][55];
int main() {
int i, j, k, N, K, M;
while(scanf("%d %d %d", &N, &K, &M) == 3) {
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(i = 1; i <= K; i++) {
for(j = 1; j <= N; j++) {
for(k = 1; k <= M; k++) {
if(j-k >= 0)
dp[i][j] += dp[i-1][j-k];
}
}
}
printf("%lld\n", dp[K][N]);
}
return 0;
}