多重集组合数简单dp

我就是我 2023-07-12 05:05 13阅读 0赞

1 #include <cstdio>
     2 #include <iostream>
     3 
     4 using namespace std;
     5 
     6 const int max_n = 1000+2;
     7 const int max_m = 1000+2;
     8 const int max_a = 1000+2;
     9 const int max_M = 1e4+2;
    10 
    11 int n,m,M;
    12 int a[max_n];
    13 int dp[max_M][max_M];
    14 // dp[i][j]:从前i件商品中，选出j个的组合数
    15 
    16 void solve()
    17 {
    18     // 初始化dp数组，无论当前有多少件，一件都不取的方法只有一种哦
    19     for(int i=0;i<=n;++i)
    20     {
    21         dp[i][0]=1;
    22     }
    23 
    24     // 从第一件物品开始取
    25     for(int i=1;i<=n;++i)
    26     {
    27         // 从取一件开始，0件时已初始化为1
    28         for(int j=1;j<=m;++j)
    29         {
    30             // 注意这里考虑最原始的搞复杂度朴素算法情况，发现有重复的，进行降复杂度变化
    31             // 数组中，考虑为数组上一行的所有可行解之和
    32             // 改为当前位置，同行前一元素与同列上一元素之和
    33             // 当前行因为最多只能取a[i]个，所以在满足j的条件下，还要考虑此种情况
    34 
    35             // j<=a[i]时，可以取遍之前元素，直接上左相加即可
    36             if(j-1-a[i] < 0)
    37             {
    38                 dp[i][j]=(dp[i-1][j] + dp[i][j-1]) % M;
    39             }
    40             // 否则只能取a[i]个
    41             // 考虑数组的动态变化过程
    42             // 所遍历的元素总数为a[i]不变，这a[i]个元素在数组中的位置，往后移了一位
    43             // 移位前一个的最先元素不满足，应减去，然后加上新加元素（即当前元素之上的元素即可）
    44             else
    45             {
    46                 dp[i][j]=(dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1-a[i]]) % M;
    47             }
    48             // 可以输出查看数组，加深理解
    49             // 也可以在出错时输出检查条件和初值
    50             //printf("%d ",dp[i][j]);
    51         }
    52         //printf("\n");
    53     }
    54 
    55     printf("%d\n",dp[n][m]);
    56 }
    57 
    58 int main()
    59 {
    60     scanf("%d %d %d",&n,&m,&M);
    61     // a[i]: 第i件商品的数量
    62     for(int i=1;i<=n;++i)
    63     {
    64         scanf("%d",&a[i]);
    65     }
    66     solve();
    67 
    68     return 0;
    69 }
    70 
    71 
    72 /*test
    73 3 3 1000
    74 1 2 3
    75 
    76 */