【BZOJ2310】ParkII
Description
Hnoi2007-Day1有一道题目 Park：给你一个 m * n 的矩阵，每个矩阵内有个权值V(i,j) (可能为负数)，要求找一条回路，使得每个点最多经过一次，并且经过的点权值之和最大，想必大家印象深刻吧．
无聊的小 C 同学把这个问题稍微改了一下：要求找一条路径，使得每个点最多经过一次，并且点权值之和最大，如果你跟小 C 一样无聊，就麻烦做一下这个题目吧．
Input
第一行 m, n，接下来 m行每行 n 个数即．
V( i,j)
Output
一个整数表示路径的最大权值之和．
Sample Input
2 3
1 -2 1
1 1 1
1 -2 1
1 1 1
Sample Output
5
【数据范围】
30%的数据，n≤6．
100%的数据，m<=100，n ≤ ≤8．
注意：路径上有可能只有一个点．
【数据范围】
30%的数据，n≤6．
100%的数据，m<=100，n ≤ ≤8．
注意：路径上有可能只有一个点．
题解：神奇游乐园的加强版，加入了独立插头，方法是用4进制数表示状态，0-无插头，1-左括号，2-右括号，3-独立插头。然后就进行4*4=16种情况的讨论吧！
注意以下几点即可：
一个独立插头可以与一个括号匹配使得另一个括号变成独立插头；新建独立插头的条件是已有独立插头数<2；一个原本匹配的插头可以自我了断，然后与它匹配的那个插头就变成独立插头了；当两个独立插头匹配时更新答案。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n,m,tot,k,ans;
int hs[270000],ref[8320],dp[2][8320],cnt[8320];
inline void upd(int x,int y)
{
if(dp[k][hs[x]]<y) dp[k][hs[x]]=y;
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
int main()
{
n=rd(),m=rd(),ans=0xc0c0c0c0;
int tmp,u,i,j,v,x,y,tag,p,q,S,T;
memset(dp[0],0xc0,sizeof(dp[0]));
for(S=0;S<(1<<(m+m+2));S++)
{
for(v=tmp=0,u=0;u<=(m<<1)&&v>=0&&tmp<=2;u+=2) x=(S>>u)&3,v+=(x==1)-(x==2),tmp+=(x==3);
if(tmp<=2&&v==0) ref[++tot]=S,cnt[tot]=tmp,hs[S]=tot;
}
dp[0][1]=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
v=rd(),ans=max(ans,v),k^=1;
memset(dp[k],0xc0,sizeof(dp[k]));
dp[k][1]=0;
for(S=1;S<=tot;S++)
{
y=j<<1,x=y-2,p=(ref[S]>>x)&3,q=(ref[S]>>y)&3,tag=dp[k^1][S]+v,T=ref[S]^(p<<x)^(q<<y);
if(!p&&!q)
{
if(cnt[S]<2)
{
if(i!=n) upd(T|(3<<x),tag);
if(j!=m) upd(T|(3<<y),tag);
}
if(i!=n&&j!=m) upd(T|(1<<x)|(2<<y),tag);
upd(T,tag-v);
}
if((!p&&q==1)||(!q&&p==1))
{
if(i!=n) upd(T|(1<<x),tag);
if(j!=m) upd(T|(1<<y),tag);
if(cnt[S]<2)
{
for(u=y+2,tmp=0;u<=(m<<1)&&tmp>=0;tmp+=((T>>u)&1)-((T>>(u+1))&1),u+=2);
u-=2;
upd(T|(1<<u),tag);
}
}
if((!p&&q==2)||(!q&&p==2))
{
if(i!=n) upd(T|(2<<x),tag);
if(j!=m) upd(T|(2<<y),tag);
if(cnt[S]<2)
{
for(u=x-2,tmp=0;u>=0&&tmp>=0;tmp+=((T>>(u+1))&1)-((T>>u)&1),u-=2);
u+=2;
upd(T|(2<<u),tag);
}
}
if((!p&&q==3)||(!q&&p==3))
{
if(i!=n) upd(T|(3<<x),tag);
if(j!=m) upd(T|(3<<y),tag);
if(!T&&ans<tag) ans=tag;
}
if(p==3&&q==3&&!T&&ans<tag) ans=tag;
if(p==2&&q==1) upd(T,tag);
if((p==1&&q==3)||(p==3&&q==1))
{
for(u=y+2,tmp=0;u<=(m<<1)&&tmp>=0;tmp+=((T>>u)&1)-((T>>(u+1))&1),u+=2);
u-=2;
upd(T|(1<<u),tag);
}
if((p==2&&q==3)||(p==3&&q==2))
{
for(u=x-2,tmp=0;u>=0&&tmp>=0;tmp+=((T>>(u+1))&1)-((T>>u)&1),u-=2);
u+=2;
upd(T|(2<<u),tag);
}
if(p==1&&q==1)
{
for(u=y+2,tmp=0;u<=(m<<1)&&tmp>=0;tmp+=((T>>u)&1)-((T>>(u+1))&1),u+=2);
u-=2;
upd(T^(3<<u),tag);
}
if(p==2&&q==2)
{
for(u=x-2,tmp=0;u>=0&&tmp>=0;tmp+=((T>>(u+1))&1)-((T>>u)&1),u-=2);
u+=2;
upd(T^(3<<u),tag);
}
}
}
for(S=tot;S>=1;S--)
{
if(!(ref[S]&3)) dp[k][S]=dp[k][hs[ref[S]>>2]];
else dp[k][S]=0xc0c0c0c0;
}
}
printf("%d",ans);
return 0;
}//2 3 1 -2 1 1 1 1