首页 > 代码库 > POJ 1038 Bugs Integrated, Inc. ——状压DP
POJ 1038 Bugs Integrated, Inc. ——状压DP
状压上面有几个方块,然后DFS转移。
复杂度貌似很高$3_{}^{20}*n$
反正过了
#include <map> #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define F(i,j,k) for (int i=j;i<=k;++i) #define D(i,j,k) for (int i=j;i>=k;--i) #define ll long long #define mp make_pair #define mask(i) ((mask%pow[i+1])/pow[i]) #define a(i) (a[x][i]) int dp[2][500005],pow[20],n,m,k; int a[205][20],t,now,pre; void print(int mask) {F(i,0,m-1)printf("%d",(mask%pow[i+1])/pow[i]);} void dfs(int x,int y,int mask,int val) { if (y>=m){dp[pre][mask]=max(val,dp[pre][mask]);return;} if (y+2<m&&!a(y)&&!a(y+1)&&!a(y+2)&&mask(y)==mask(y+1)&&mask(y+1)==mask(y+2)) { if (mask(y)==1) { mask-=pow[y]+pow[y+1]+pow[y+2]; dfs(x,y+3,mask,val+1); mask+=pow[y]+pow[y+1]+pow[y+2]; } else { mask+=pow[y]+pow[y+1]+pow[y+2]; dfs(x,y+3,mask,val); mask-=pow[y]+pow[y+1]+pow[y+2]; } } if (y+1<m&&!a(y)&&!a(y+1)&&mask(y)==mask(y+1)) { if (mask(y)<2) { mask+=pow[y]+pow[y+1]; dfs(x,y+2,mask,val); mask-=pow[y]+pow[y+1]; } else { mask-=2*pow[y]+2*pow[y+1]; dfs(x,y+2,mask,val+1); mask+=2*pow[y]+2*pow[y+1]; } } if (!mask(y)) { dfs(x,y+1,mask,val); } } int main() { scanf("%d",&t); pow[0]=1; F(i,1,14)pow[i]=pow[i-1]*3; while (t--) { memset(a,0,sizeof a); scanf("%d%d%d",&n,&m,&k); F(i,1,k) { int x,y;scanf("%d%d",&x,&y); x--; y--; a[x][y]=1; } F(i,0,m-1) a[n][i]=1; now=1;pre=0; memset(dp[pre],-1,sizeof dp[pre]); dp[pre][0]=0; F(i,0,n) { now^=1; pre^=1; memset(dp[pre],-1,sizeof dp[pre]); F(j,0,pow[m]-1) if (~dp[now][j]) { dfs(i,0,j,dp[now][j]); } } printf("%d\n",dp[pre][0]); } }
POJ 1038 Bugs Integrated, Inc. ——状压DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。