1193 - Dice (II) PDF (English) Statistics ForumTime Limit: 3 second(s) Memory Limit: 32 MBYou have N dices; each of them has K faces numbered from 1 to K. Now you can arrange the N dices in a line. If the summation of the top faces of the dices is S, you calculate the score as the multiplication of all the top faces.
Now you are given N, K, S; you have to calculate the summation of all the scores.
InputInput starts with an integer T (≤ 25), denoting the number of test cases.
Each case contains three integers: N (1 ≤ N ≤ 1000) K (1 ≤ K ≤ 1000) S (0 ≤ S ≤ 15000).
OutputFor each case print the case number and the result modulo 100000007.
Sample InputOutput for Sample Input51 6 32 9 8500 6 1000800 800 100002 100 10Case 1: 3Case 2: 84Case 3: 74335590Case 4: 33274428Case 5: 165
解题思路: 跟(I)一样分析可得dp[i][j] = dp[i-1][j-1]+dp[i-1][j-2]*2 + ……+dp[i-1][j-k]*k;
则dp[i][j-1] = dp[i-1][j-2]+dp[i-1][j-3]*2 + ……+dp[i-1][j-k-1]*k;
比较可得dp[i][j]=dp[i][j-1] - dp[i-1][j-k-1]*k + sum[i-1][j-1]-sum[i-1][j-k-1];
sum[i][j]为dp[i][j] 的第i层的前j项和。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int mod = 100000007; const int N = 1010,S = 15010; long long dp[2][S],sum[2][S]; int main(){ int T,n,k,s; scanf("%d",&T); for(int t=1;t<=T;t++){ memset(dp,0,sizeof(dp)); memset(sum,0,sizeof(sum)); scanf("%d%d%d",&n,&k,&s); for(int i=1;i<=k;i++) dp[1][i] = i,sum[1][i] = sum[1][i-1]+i; for(int i=k+1;i<=s;i++) sum[1][i] = sum[1][i-1]; for(int i=2;i<=n;i++){ for(int j=1;j<=s;j++){ dp[i%2][j] = (dp[i%2][j-1] + sum[(i+1)%2][j-1] - sum[(i+1)%2][max(0,j-k-1)]-(dp[(i+1)%2][max(0,j-k-1)]*k)%mod+mod)%mod; sum[i%2][j] = sum[i%2][j-1] + dp[i%2][j]; } } printf("Case %d: %lld\n",t,dp[n%2][s]); } return 0; }
转载于:https://www.cnblogs.com/yuanshixingdan/p/5568854.html
相关资源：JAVA上百实例源码以及开源项目