当前位置:编程学习 > C/C++ >>

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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,