[HRBUST1472]Coin（dp，计数）

题目链接：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。

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const LL mod = ;

 const int maxn = ;

 LL dp[maxn][maxn][maxn];

 int n, m;

 LL dfs(int n, int m, int pre) {

     if(dp[n][m][pre] != -) return dp[n][m][pre];

     // if(pre > m) return dp[n][m][pre] = 0;

     if(n == ) {

         if(m == ) return dp[n][m][pre] = ;

         return dp[n][m][pre] = ;

     }

     dp[n][m][pre] = ;

     for(int i = pre; i <= m; i++) {

         if(m - i < ) break;

         dp[n][m][pre] = (dp[n][m][pre] + dfs(n-, m-i, i)) % mod;

     }

     return dp[n][m][pre];

 }

 int main() {

     // freopen("in", "r", stdin);

     int T;

     scanf("%d", &T);

     memset(dp, , sizeof(dp));

     dp[][][] = ;

     for(int i = ; i <= ; i++) {

         for(int j = ; j <= ; j++) {

             for(int k = ; k <= ; k++) {

                 if(dp[i][j][k] == ) continue;

                 for(int l = k; j + l <= ; l++) {

                     if(l > j + ) break;

                     dp[i+][j+l][l] = (dp[i+][j+l][l] + dp[i][j][k]) % mod;

                 }

             }

         }

     }

     while(T--) {

         scanf("%d%d",&n,&m);

         LL ret = ;

         for(int i = ; i <= m; i++) {

             ret = (ret + dp[n][m][i]) % mod;

         }

         printf("%lld\n", ret);

     }

     return ;

 }

巴特西

[HRBUST1472]Coin（dp，计数）

最新文章

热门文章