light oj 1145 - Dice (I) DP计数
题意: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
补充:软件开发 , C++ ,