首页 > 代码库 > [HRBUST1472]Coin（dp，计数）

[HRBUST1472]Coin（dp，计数）

2024-08-25 08:12:14   218人阅读

题目链接：http://acm-software.hrbust.edu.cn/problem.php?id=1472

题意：给n个硬币，面值随意。问恰好凑成m元的种类数（去掉重复）。

dp(i,j,k)表示i个硬币，j元，最大是k时的种类数。

一开始智障记忆化dfs暴T不止，转成递推还是会T。

结果就考虑先给记忆化dfs加一些剪枝，还是T。

再给递推做一些处理，发现是因为枚举当前最大的时候，最大的l如果是j+2了，即使只有它一个，也是大于j+1了。换到这里来看，是前向着递推，那也就是说，题目所述最小面值是1，在递推的时候仅仅维持在j内是不满足的，需要j+1。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const LL mod = 2000000007;
 5 const int maxn = 220;
 6 LL dp[maxn][maxn][maxn];
 7 int n, m;
 8 
 9 LL dfs(int n, int m, int pre) {
10     if(dp[n][m][pre] != -1) return dp[n][m][pre];
11     // if(pre > m) return dp[n][m][pre] = 0;
12     if(n == 0) {
13         if(m == 0) return dp[n][m][pre] = 1;
14         return dp[n][m][pre] = 0;
15     }
16     dp[n][m][pre] = 0;
17     for(int i = pre; i <= m; i++) {
18         if(m - i < 0) break;
19         dp[n][m][pre] = (dp[n][m][pre] + dfs(n-1, m-i, i)) % mod;
20     }
21     return dp[n][m][pre];
22 }
23 
24 int main() {
25     // freopen("in", "r", stdin);
26     int T;
27     scanf("%d", &T);
28     memset(dp, 0, sizeof(dp));
29     dp[1][1][1] = 1;
30     for(int i = 1; i <= 200; i++) {
31         for(int j = 1; j <= 200; j++) {
32             for(int k = 1; k <= 200; k++) {
33                 if(dp[i][j][k] == 0) continue;
34                 for(int l = k; j + l <= 200; l++) {
35                     if(l > j + 1) break;
36                     dp[i+1][j+l][l] = (dp[i+1][j+l][l] + dp[i][j][k]) % mod;
37                 }
38             }
39         }
40     }
41     while(T--) {
42         scanf("%d%d",&n,&m);
43         LL ret = 0;
44         for(int i = 1; i <= m; i++) {
45             ret = (ret + dp[n][m][i]) % mod;
46         }
47         printf("%lld\n", ret);
48     }
49     return 0;
50 }

 

[HRBUST1472]Coin（dp，计数）


联系
我们