设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

codeforces 118D Caesar's Legions 背包问题

2012-11-11 21:50:00.0  
导读:题意:求序列数。这个序列里不能有连续k1个footmen还有k2个horsemen。做法:这种有固定资源,并且有离散化消耗的,一定要忘背包上靠。#include#define mod 100000000#define LL long longLL dp[2][202][102];int main(void){ int n1,n2,k1,k2; int i,j,t; scanf("...。。。

题意:求序列数。这个序列里不能有连续k1个footmen还有k2个horsemen。

做法:这种有固定资源,并且有离散化消耗的,一定要忘背包上靠。

#include#define mod 100000000#define LL long longLL dp[2][202][102];int main(void){    int n1,n2,k1,k2;    int i,j,t;    scanf("%d%d%d%d",&n1,&n2,&k1,&k2);    dp[0][0][0]=dp[1][0][0]=1;    for(i=1;i<=n1+n2;i++)    {        for(j=n1>i?i:n1;j>=1;j--)          for(t=1;t<=j&&t<=k1;t++)           if(n2>=i-j)             dp[0][i][j]=(dp[0][i][j]+dp[1][i-t][i-j])%mod;        for(j=n2>i?i:n2;j>=1;j--)          for(t=1;t<=j&&t<=k2;t++)            if(n1>=i-j)              dp[1][i][j]=(dp[1][i][j]+dp[0][i-t][i-j])%mod;    }    printf("%I64d\n",(dp[0][n1+n2][n1]+dp[1][n1+n2][n2])%mod);    return 0;}


(编辑: cqlf__)

网友评论
相关文章