首页 > 代码库 > HDU 4301 Divide Chocolate DP
HDU 4301 Divide Chocolate DP
题目链接~http://acm.hdu.edu.cn/showproblem.php?pid=4301
非原创,看了好几个大神的题解,才看懂
代码::刚开始看bin神的,看了半天没看懂,我太菜了 %>_<%
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 /* 5 dp[i][j][0] 表示前i行出现了j部分 且第i行那两个不是一部分的 6 dp[i][j][1] 表示前i行出现了j部分 且第i行那两个是一部分的 7 8 状态的话 9 第一种情况是 在第i行j不变10 dp[i][j][1]=dp[i-1][j][0]*2+dp[i-1][j][1] ; dp[i][j][0]=dp[i-1][j][0]; 11 12 第二种情况是 在第i行j+113 dp[i][j][1]=dp[i-1][j-1][0]+dp[i-1][j-1][1]; dp[i][j][0]=2*dp[i-1][j-1][1]+2*dp[i-1][j-1][0]; 14 第三种情况是 在第i行j+215 dp[i][j][0]=dp[i-1][j-2][1]+dp[i-1][j-2][0]; 16 */17 18 int dp[1005][2005][3]={0}; 19 int main() 20 { 21 int n,x,y; 22 dp[1][1][1]=1;dp[1][2][0]=1;23 for(int i=2;i<=1002;i++)24 { 25 for(int j=1;j<=i*2;j++)26 { 27 dp[i][j][1]=(2*dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j-1][0]+dp[i-1][j-1][1])%100000007; 28 dp[i][j][0]=(dp[i-1][j][0]+2*dp[i-1][j-1][1]+2*dp[i-1][j-1][0]+dp[i-1][j-2][0]+dp[i-1][j-2][1])%100000007; 29 } 30 } 31 scanf("%d",&n); 32 while(n--)33 { 34 scanf("%d%d",&x,&y); 35 printf("%d\n",(dp[x][y][1]+dp[x][y][0])%100000007); 36 } 37 return 0; 38 }
HDU 4301 Divide Chocolate DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。