首页 > 代码库 > HDU 2512 一卡通大冒险

HDU 2512 一卡通大冒险

2024-07-14 07:15:18   224人阅读

我感觉这更像个数学问题。

dp[i][j]表示将i件物品分成j组的方案数。

状态转移方程：

dp[i][j] = dp[i-1][j-1] + j * dp[i-1][j];

将i张卡分成j组可以有之前两种情况得来：i-1张卡分成j-1组，只要将第i张卡独立分成一组就行了，或者是i-1张卡分成j组，第i张卡随便插入哪一组都符合条件。

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 const int maxn = 2005; 8 int dp[maxn][maxn]; 9 10 int main(void)11 {12     #ifdef LOCAL13         freopen("2512in.txt", "r", stdin);14     #endif15 16     int i, j;17     for(i = 1; i <= 2000; ++i)18     {19         dp[i][1] = 1;20         dp[i][i] = 1;21     }22     for(i = 2; i <= 2000; ++i)23         for(j = 2; j < i; ++j)24             dp[i][j] = (dp[i-1][j-1] + j * dp[i-1][j]) % 1000;25 26     int n, num, sum;27     scanf("%d", &n);28     while(n--)29     {30         scanf("%d", &num);31         sum = 0;32         for(i = 1; i <= num; ++i)33             sum = (sum + dp[num][i]) % 1000;34         printf("%d\n", sum);35     }36     return 0;37 }
代码君

 


联系
我们