2012-11-28 08:01:55Morris
[PTC][201211] PD Happy Teachers’ Day
動規作法，dp[n][m] n 個東西 m 堆。
dp[n+1][j] += dp[n][j]*j (選其中一堆, j 種可能)
dp[n+1][j+1] += dp[n][j] (多開一堆)
#include <stdio.h>
long long dp[2005][2005];
int main() {
int n, i, j;
int ans[2005] = {};
dp[1][1] = 1;
for(i = 1; i <= 2000; i++) {
for(j = 1; j <= i; j++) {
ans[i] += dp[i][j];
if(ans[i] >= 9999997)
ans[i] -= 9999997;
dp[i+1][j] += (dp[i][j]*j)%9999997;
dp[i+1][j+1] += dp[i][j];
dp[i+1][j] %= 9999997;
dp[i+1][j+1] %= 9999997;
}
}
while(scanf("%d", &n) == 1)
printf("%d\n", ans[n]);
return 0;
}
dp[n+1][j] += dp[n][j]*j (選其中一堆, j 種可能)
dp[n+1][j+1] += dp[n][j] (多開一堆)
#include <stdio.h>
long long dp[2005][2005];
int main() {
int n, i, j;
int ans[2005] = {};
dp[1][1] = 1;
for(i = 1; i <= 2000; i++) {
for(j = 1; j <= i; j++) {
ans[i] += dp[i][j];
if(ans[i] >= 9999997)
ans[i] -= 9999997;
dp[i+1][j] += (dp[i][j]*j)%9999997;
dp[i+1][j+1] += dp[i][j];
dp[i+1][j] %= 9999997;
dp[i+1][j+1] %= 9999997;
}
}
while(scanf("%d", &n) == 1)
printf("%d\n", ans[n]);
return 0;
}