首页 > 代码库 > dp 斯特林数 HDU2512一卡通大冒险

dp 斯特林数 HDU2512一卡通大冒险

这道题其实就是斯特林数,找不同的集合,一共有多少中组法,递推式就是dp[n][k] = dp[n - 1][k - 1] + k * dp[n - 1][k];

这个式子可以这么解释,dp[n][k]就是总数为n分成k个集合一共有多少种, 它就有两种情况一种是第一个自己一个集合(也就是他自己一堆), 那么这种情况下的种类就是dp[n - 1][k - 1],就是剩下的n -1 个有k -1堆, 还有一种就是先把第一个拿出来,然后将剩下的n- 1个分成k个集合, 然后再把第一个随便放入一个, 但是它可以有k中放法,所以就是k * dp[n - 1][k];

代码如下:

 1 #include<iostream> 2 #include <stdio.h> 3  4 using namespace std; 5 int dp[2002][2002]; 6 int main() 7 { 8     for (int i = 0; i < 2002; i++) 9         dp[i][0] = 0, dp[i][i] = 1;10     dp[2][1] = 1;11     dp[3][1] = 1;12     dp[3][2] = 3;13     for (int i = 4; i < 2002; i++)14     {15         for (int j = 1; j < i; j++)16         {17             dp[i][j] = (dp[i - 1][j - 1] + j * dp[i - 1][j]) % 1000;18         }19     }20     int n;21     scanf("%d", &n);22     while (n--)23     {24         int x;25         scanf("%d", &x);26         int res = 0;27         for (int i = 1; i <= x; i++)28         {29             res += dp[x][i];30         }31         res %= 1000;32         printf("%d\n", res);33     }34     35     return 0;36 }

 

dp 斯特林数 HDU2512一卡通大冒险