首页 > 代码库 > BZOJ 1087 状压DP
BZOJ 1087 状压DP
先预处理出每一行的可行状压值存入mark,并记录该值所含点数sum
处理每相邻两行的状压值是否可行存入 dis
DP方程:dp[i][l][k+sum[l]]+=dp[i-1][j][k]; 第i行l状态一共放了k+sum[l]+=上一行j状态放k个的方案数
#include "stdio.h" #include "string.h" int b[21]; int n,m,i,j,l,k,cnt; long long ans,dp[2][101][90]; int dis[101][101],sum[101],mark[101]; int get(int x) { int sum; sum=0; while (x!=0) { sum+=x%2; x/=2; } return sum; } int judge1(int x) { if (x&(x<<1)) return 0; if (x&(x>>1)) return 0; return 1; } int judge2(int x,int y) { if (x&y) return 0; if (x&(y<<1)) return 0; if (x&(y>>1)) return 0; return 1; } int main() { b[0]=1; for (i=1;i<=10;i++) b[i]=b[i-1]*2; while (scanf("%d%d",&n,&m)!=EOF) { cnt=0; for (i=0;i<b[n];i++) if (judge1(i)==1) { cnt++; mark[cnt]=i; sum[cnt]=get(i); } memset(dis,0,sizeof(dis)); for (i=1;i<=cnt;i++) for (j=1;j<=cnt;j++) if (judge2(mark[i],mark[j])==1) dis[i][j]=1; memset(dp,0,sizeof(dp)); dp[0][1][0]=1; for (i=1;i<=n;i++) { memset(dp[i%2],0,sizeof(dp[i%2])); for (j=1;j<=cnt;j++) for (k=0;k<=m;k++) if (dp[1-i%2][j][k]) for (l=1;l<=cnt;l++) if (dis[j][l]&&k+sum[l]<=m) dp[i%2][l][k+sum[l]]+=dp[1-i%2][j][k]; } ans=0; for (i=1;i<=cnt;i++) ans+=dp[n%2][i][m]; printf("%lld\n",ans); } return 0; }
BZOJ 1087 状压DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。