首页 > 代码库 > HDU 1693 Eat the Trees
HDU 1693 Eat the Trees
第一道(可能也是最后一道)插头dp。。。。
总算是领略了它的魅力。。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; long long t,n,m,map[15][15],dp[15][15][(1<<12)+1]; void work(long long x) { scanf("%I64d%I64d",&n,&m); for (long long i=1;i<=n;i++) for (long long j=1;j<=m;j++) scanf("%I64d",&map[i][j]); memset(dp,0,sizeof(dp)); dp[0][m][0]=1; for (long long i=1;i<=n;i++) { for (long long j=0;j<(1<<m);j++) dp[i][0][j<<1]=dp[i-1][m][j]; for (long long j=1;j<=m;j++) for (long long k=0;k<(1<<(m+1));k++) { long long r1=(1<<(j-1)),r2=(1<<j); if (map[i][j]) { if ((k&r1) && (k&r2)) dp[i][j][k]=dp[i][j-1][k^r1^r2]; else if ((!(k&r1)) && (!(k&r2))) dp[i][j][k]=dp[i][j-1][k+r1+r2]; else dp[i][j][k]=dp[i][j-1][k]+dp[i][j-1][k^r1^r2]; } else { if ((!(k&r1)) && (!(k&r2))) dp[i][j][k]=dp[i][j-1][k]; else dp[i][j][k]=0; } } } printf("Case %I64d: There are %I64d ways to eat the trees.\n",x,dp[n][m][0]); } int main() { scanf("%I64d",&t); for (long long i=1;i<=t;i++) work(i); return 0; }
HDU 1693 Eat the Trees
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。