首页 > 代码库 > hdu 4301(基本dp)
hdu 4301(基本dp)
题意:就是给你一块2*n的巧克力,让你把它分成x块,并且每一个单位的巧克力各不相同,问有多少种分法?
分析:用dp[i][j][k],表示到巧克力的第二列时,巧克力被分成了j快,k用来表示第i列上下两块是分开的还是在一起的,在纸上把所有的情况画一下,于是就得到状态方程:
dp[i][j][0]=(dp[i-1][j][1]*2+dp[i-1][j][0]+dp[i-1][j-1][0]+dp[i-1][j-1][1])%mod;
dp[i][j][1]=(dp[i-1][j][1]+dp[i-1][j-1][0]*2+dp[i-1][j-1][1]*2+dp[i][j][1]+dp[i-1][j-2][0]+dp[i-1][j-2][1])%mod;
代码实现:
#include<stdio.h>#include<string.h>#include<math.h>#define mod 100000007 int dp[1005][2005][2];void init(){ int i,j; memset(dp,0,sizeof(dp)); dp[1][1][0]=1; dp[1][2][1]=1; for(i=1;i<=1000;i++) for(j=1;j<=2000;j++) { if(dp[i][j][0]==0) dp[i][j][0]=(dp[i-1][j][1]*2+dp[i-1][j][0]+dp[i-1][j-1][0]+dp[i-1][j-1][1])%mod; if(dp[i][j][1]==0) { dp[i][j][1]=(dp[i-1][j][1]+dp[i-1][j-1][0]*2+dp[i-1][j-1][1]*2)%mod; if(j-2>=0) { dp[i][j][1]=(dp[i][j][1]+dp[i-1][j-2][0]+dp[i-1][j-2][1])%mod; } } }}int main(){ init(); int T,n,m; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); printf("%d\n",(dp[n][m][0]+dp[n][m][1])%mod); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。