题目链接：http://lightoj.com/volume_showproblem.php?problem=1191

1191 - Bar Codes    PDF (English)StatisticsForum Time Limit: 0.5 second(s)Memory Limit: 32 MB

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' represents 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

Input starts with an integer T (≤ 20000), denoting the number of test cases.

Each case contains three integers: n, k, m (1 ≤ k, m ≤ n ≤ 50).

Output

For each case, print the case number and BC(n, k, m).

Sample Input

Output for Sample Input

2

7 4 3

7 4 2

Case 1: 16

Case 2: 4

 

---

PROBLEM SETTER: MD. KAMRUZZAMAN SPECIAL THANKS: JANE ALAM JAN (SOLUTION, DATASET)

题意：输入n,k,m，制作条形码，n个位置，每一块最多m个，分成k块的，0（或者1）是一块，求所有的方案数

解析：DFS，直接记忆化搜索，dp[n][m][k]  =  dp[1 -> t ][m][k^1]  其中 t = min(n, k)

代码：

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<vector> #include<queue> #include<map> #include<cmath> #define N 59 using namespace std; const int INF = 0x3f3f3f3f; long long dp[N][N][N][2]; //last指最后一块 long long dfs(long long n, long long m, long long k, long long last) { if(dp[n][m][k][last] != -1) return dp[n][m][k][last]; long long &res = dp[n][m][k][last]; if(n == 0) { if(m == 0 && last == 0) return res = 1; return res = 0; } if(m == 0) { if(n == 0 && last == 0) return res = 1; return 0; } long long t = min(n, k); res = 0; for(long long i = 1; i <= t; i++) { res += dfs(n - i, m - 1, k, last^1); } return res; } int main() { memset(dp, -1, sizeof(dp)); int n, m, k, t, cnt = 0; scanf("%d", &t); while(t--) { scanf("%d%d%d", &n, &m, &k); printf("Case %d: %lld\n", ++cnt, dfs(n, m, k, 0) + dfs(n, m, k, 1)); } return 0; }