題意：n個骰子，每個骰子都有k個面,數字分別為1~k
問：n個骰子最上面的面的數字加起來為S的擺放方案共有幾種
憑感覺可以聯想到這樣一種DP
dp[i][j]表示前i個骰子的和小於等於j時的總方案數，然後轉移的時候可以這樣
dp[i+1][j]=dp[i+1][j-1]+(dp[i][j-1]-dp[i][j-k-1]) (j-k-1>=0,要不然就是0)
dp[i+1][j-1]是小於j的方案總數，後面這個自然是等於j的方案總數因為前i個骰子組成
j-k ~ j-1之間的數時都可以通過加上第i+1個骰子的數組成j，所以應該加上後面這個差
好了，既然都設計好了，那就寫吧，但一看，數據范圍--！，n=1000,S=15000,
給了兩秒，時間可以過，空間就卡了，
仔細一想，當前層的狀態只需要上一層的狀態就夠了
，以前的狀態不用保存，所以用滾動空間來保存吧
[cpp]
#include<cstdio>
#include<cstring>
typedef long long lld;
const lld mod = 100000007;
const int maxn = 15010;
lld dp[2][maxn];
int n,k,s;
lld get(int a,int l,int r)
{
lld x=0;
l-=1;
if(l>=0) x=dp[a][l];
lld y=dp[a][r];
return y-x;
}
lld solve()
{
memset(dp,0,sizeof(dp));
int a=0,b=1;
for(int i=0;i<=s;i++) dp[a][i]=1;
for(int i=0;i<n;i++)
{
dp[b][0]=0;
for(int j=1;j<=s;j++)
{
dp[b][j]=dp[b][j-1]+get(a,j-k,j-1);
dp[b][j]%=mod;
}
a^=1;
b^=1;
}
return (get(a,s,s)%mod+mod)%mod;
}
int main()
{
int t,ca=1;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&k,&s);
printf("Case %d: %lld\n",ca++,solve());
}
return 0;
}
作者：haha593572013
