P3190 [HNOI2007]神奇游乐园
Description
给你一个 (m * n) 的矩阵，每个矩阵内有个权值(V(i,j)) (可能为负数)，要求找一条回路，使得每个点最多经过一次，并且经过的点权值之和最大。
Input
输入文件中的第一行为两个正整数(n)和(m)，表示游乐场的大小为(n*m)。因为这个娱乐场很狭窄，所以(n)和(m)满足：(2le nle 100)，(2le mle 6)。接下来的(n)行，每行有(m)个整数，第(i)行第(j)列表示游乐场的第(i)行第(j)列的小格子中的娱乐项目的满意度，这个满意度的范围是([-1000，1000])。同一行的两个整数之间用空格隔开。
Output
输出文件中仅一行为一个整数，表示最高的满意度之和。
注意几个问题
-
什么时候更新答案？
当前格子左边是(1)，上边是(2)且除去这个(1)和(2)后的状态上没有插头。
-
每次新一行的时候我们会把状态数组向右移动两位，这时候会当(n)比较大的时候出现负数，在插入(Hash)表取模后需要把(Ta)变成正数。
当然也可以有其他的方法，用无符号整型自然溢出或者手动每次(&)一个状态内全是(1)，其余的位置全是(0)的数字。实测每次(&)的速度是最快的，大概是其他两个的(1/8)。
- 其实写的漂亮并不会出现负数
- 但是一出现可能挂的很惨哦
-
在伸出插头时一定要注意边界，不能越过(n)和(m)
Code:
#include <cstdio>
#include <cstring>
const int N=3e5;
const int mod=299987;
int n,m,cur,bit[12],ans=-0x3f3f3f3f,a[110][10];
int head[N],to[N],Next[N],cnt[2],tot,dp[2][N],sta[2][N],del;
void Ins(int s,int val)
{
s=s&del;
int x=s%mod;
for(int i=head[x];i;i=Next[i])
if(sta[cur][to[i]]==s)
{
dp[cur][to[i]]=dp[cur][to[i]]>val?dp[cur][to[i]]:val;
return;
}
sta[cur][++cnt[cur]]=s;
dp[cur][cnt[cur]]=val;
to[++tot]=cnt[cur];
Next[tot]=head[x];
head[x]=tot;
}
void DP()
{
dp[cur][++cnt[cur]]=0,sta[cur][cnt[cur]]=0;
for(int i=1;i<=n;i++)
{
for(int s=1;s<=cnt[cur];s++) sta[cur][s]=(sta[cur][s]<<2)&(del);
for(int j=1;j<=m;j++)
{
cur^=1;
tot=cnt[cur]=0;
memset(head,0,sizeof(head));
for(int s=1;s<=cnt[cur^1];s++)
{
int lassta=sta[cur^1][s],lasans=dp[cur^1][s];
int sr=lassta>>bit[j-1]&3,sd=lassta>>bit[j]&3;
if(!sr&&!sd)
{
Ins(lassta,lasans);//没选
Ins(lassta|(1<<bit[j-1])|(2<<bit[j]),lasans+a[i][j]);//选
}
else if(!sr&&sd)
{
if(j<m) Ins(lassta,lasans+a[i][j]);
if(i<n) Ins((lassta|(sd<<bit[j-1]))&(~(sd<<bit[j])),lasans+a[i][j]);
}
else if(sr&&!sd)
{
if(i<n) Ins(lassta,lasans+a[i][j]);
if(j<m) Ins((lassta|(sr<<bit[j]))&(~(sr<<bit[j-1])),lasans+a[i][j]);
}
else if(sr==1&&sd==1)
{
int ct=1;
for(int k=j+2;k<=m;k++)
{
if((lassta>>bit[k-1]&3)==1) ++ct;
if((lassta>>bit[k-1]&3)==2) --ct;
if(!ct)
{
Ins((lassta&(~(sr<<bit[j-1])&(~(sd<<bit[j]))))-(1<<bit[k-1]),lasans+a[i][j]);
break;
}
}
}
else if(sr==2&&sd==2)
{
int ct=1;
for(int k=j-1;k;k--)
{
if((lassta>>bit[k-1]&3)==2) ++ct;
if((lassta>>bit[k-1]&3)==1) --ct;
if(!ct)
{
Ins((lassta&(~(sr<<bit[j-1])&(~(sd<<bit[j]))))+(1<<bit[k-1]),lasans+a[i][j]);
break;
}
}
}
else if(sr==2&&sd==1)
Ins(lassta&(~(sr<<bit[j-1])&(~(sd<<bit[j]))),lasans+a[i][j]);
else if(sr==1&&sd==2&&!(lassta&(~(sr<<bit[j-1]))&(~(sd<<bit[j]))&del))
ans=ans>lasans+a[i][j]?ans:lasans+a[i][j];
}
}
}
}
int main()
{
for(int i=1;i<=10;i++) bit[i]=i<<1;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
del=(1<<(m+1<<1|1))-1;
DP();
printf("%d
",ans);
return 0;
}
2018.12.20