LightOJ1326 Race（DP）

题目问N匹马比赛有多少种结果。一开始想用排列组合搞搞，然后发现想错了。艰难地把思路转向DP，最后AC了。

dp[i][j]表示前i匹马确定出j个名次的方案数
dp[1][1]=1
对于第i匹马，它要确定出j个名次：要嘛前i-1匹确定出j个次名，然后第i匹可以成为第1...j名；要嘛前i-1匹确定出j-1个名次，然后第i匹成为独立的新的一个名次，也有第1..j名j种选择。
所以状态转移方程是：dp[i][j]=d[i-1][j]*j+d[i-1][j-1]*j

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int d[1001][1001];
 5 int main(){
 6     d[1][1]=1;
 7     for(int i=2; i<1001; ++i){
 8         for(int j=1; j<=i; ++j){
 9             d[i][j]=d[i-1][j]*j+d[i-1][j-1]*j;
10             d[i][j]%=10056;
11         }
12     }
13     int t,n;
14     scanf("%d",&t);
15     for(int cse=1; cse<=t; ++cse){
16         scanf("%d",&n);
17         int res=0;
18         for(int i=1; i<=n; ++i){
19             res+=d[n][i];
20             res%=10056;
21         }
22         printf("Case %d: %d
",cse,res);
23     }
24     return 0;
25 }