admin 管理员组

文章数量: 887006

bzoj1187: [HNOI2007]神奇游乐园

这是一道插头DP。。。不会的可以看一下《基于连通性状态压缩的动态规划问题》ppt

然后就是裸题了？

预处理出所有合法的状态，以及每种状态的每个插头匹配的位置，DP时间复杂度O(2^m*n*m)。

分9种情况写的也是乱的。。

#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 1e9
using namespace std;
int n,m,a,tot,dp[2][30000],q[18000],bit[30],Ans=-inf,top,st[100],cnt,now,num,lst;
int S[18000][10];
void pre(int x,int p)
{top=0; for(int i=1;i<=m+1;i++,p>>=2){if((p&3)==2)st[++top]=i;else if((p&3)==1){if(top==0){cnt--;return;}S[x][st[top]]=i;S[x][i]=st[top];top--;}else S[x][i]=0;}if(top)cnt--;
}
void Get(int x,int p)
{if(x>m+1)q[++cnt]=p,pre(cnt,p);else Get(x+1,p<<2),Get(x+1,p<<2|1),Get(x+1,p<<2|2);
}
void up(int &x,int y){if(y>x)x=y;}
int make(int a,int b)
{if(a&bit[b<<1])return 1;if(a&bit[(b<<1)-1])return 2;return 0;
}
int main()
{memset(dp,192,sizeof dp);for(int i=1;i<=20;i++) bit[i]=1<<(i-1);scanf("%d%d",&n,&m);Get(1,0);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&a);lst=tot;tot^=1;for(int k=1;k<=cnt;k++) dp[lst][q[k]]=-inf;dp[tot][0]=0;for(int k=1;k<=cnt;k++){now=q[k];num=dp[tot][now]+a;int x=make(now,j),y=make(now,j+1);//以下分类讨论。。if(!x){if(!y){up(dp[lst][now],dp[tot][now]);if(i!=n&&j!=m)up(dp[lst][now|bit[j<<1]|bit[((j+1)<<1)-1]],num);}else if(y&1){if(j!=m)up(dp[lst][now],num);if(i!=n)up(dp[lst][now^bit[(j+1)<<1]|bit[j<<1]],num);}else if(y&2){if(j!=m)up(dp[lst][now],num);if(i!=n)up(dp[lst][now^bit[((j+1)<<1)-1]|bit[(j<<1)-1]],num);}}else if(x&1){if(!y){if(i!=n)up(dp[lst][now],num);if(j!=m)up(dp[lst][now^bit[j<<1]|bit[(j+1)<<1]],num);}else if(y&1){up(dp[lst][now^bit[j<<1]^bit[(j+1)<<1]^(bit[(S[k][j+1]<<1)-1]*3)],num);}else if(y&2){if((now^bit[j<<1]^bit[((j+1)<<1)-1])==0)up(Ans,num);}}else if(x&2){if(!y){if(i!=n)up(dp[lst][now],num);if(j!=m)up(dp[lst][now^bit[(j<<1)-1]|bit[((j+1)<<1)-1]],num);}else if(y&1){up(dp[lst][now^bit[(j<<1)-1]^bit[(j+1)<<1]],num);}else if(y&2){up(dp[lst][now^bit[(j<<1)-1]^bit[((j+1)<<1)-1]^(bit[(S[k][j]<<1)-1]*3)],num);}}}if(j==m){lst=tot;tot^=1;for(int k=1;k<=cnt;k++)dp[lst][q[k]]=-inf;for(int k=1;k<=cnt;k++)dp[lst][q[k]<<2]=dp[tot][q[k]];	}}printf("%d\n",Ans);return 0;
}


本文标签： bzoj1187 HNOI2007神奇游乐园

版权声明：本文标题：bzoj1187: [HNOI2007]神奇游乐园 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732361015h1535218.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。