首页 > 代码库 > BZOJ 1087状态压缩DP
BZOJ 1087状态压缩DP
状态压缩DP真心不会写,参考了别人的写法。
先预处理出合理状态,
我们用二进制表示可以放棋子的状态,DP[I][J][K]:表示现在处理到第I行,J:表示第I行的状态,K表示现在为止一共放的棋子数量。
#include<stdio.h>#include<iostream>#define N 1111using namespace std;typedef long long ll;int num,n,m;ll dp[11][1<<11][90];int hh[N],hnum[N];int mp[1111][1111];int check(int x,int y){ if (x&(y<<1)) return 0; if (x&(y>>1)) return 0; if (x&y) return 0; return 1;}int judge(int x){ if (x&(x<<1)) return 0; if (x&(x>>1)) return 0; return 1;}int getsum(int x){ int ans=0; while (x) { if (x&1) ans++; x>>=1; } return ans;}void pre(){ num=0; for (int i=0;i<(1<<n);i++) if (judge(i)) { hh[++num]=i; hnum[num]=getsum(i); } for (int i=1;i<=num;i++) for (int j=1;j<=num;j++) if (check(hh[i],hh[j])) mp[i][j]=mp[j][i]=1;}int main(){ cin>>n>>m; pre(); dp[0][1][0]=1; for (int i=0;i<n;i++) for (int j=1;j<=num;j++) for (int k=0;k<=m;k++) if (dp[i][j][k]) for (int p=1;p<=num;p++) if (mp[j][p]&&k+hnum[p]<=m) dp[i+1][p][k+hnum[p]]+=dp[i][j][k]; ll ans=0; for (int i=1;i<=num;i++) ans+=dp[n][i][m]; cout<<ans<<endl; return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。