洛谷 P3190 [HNOI2007]神奇游乐园 解题报告

时间:2021-02-18 19:34:14

P3190 [HNOI2007]神奇游乐园

Description

给你一个 \(m * n\) 的矩阵,每个矩阵内有个权值\(V(i,j)\) (可能为负数),要求找一条回路,使得每个点最多经过一次,并且经过的点权值之和最大。

Input

输入文件中的第一行为两个正整数\(n\)和\(m\),表示游乐场的大小为\(n*m\)。因为这个娱乐场很狭窄,所以\(n\)和\(m\)满足:\(2\le n\le 100\),\(2\le m\le 6\)。接下来的\(n\)行,每行有\(m\)个整数,第\(i\)行第\(j\)列表示游乐场的第\(i\)行第\(j\)列的小格子中的娱乐项目的满意度,这个满意度的范围是\([-1000,1000]\)。同一行的两个整数之间用空格隔开。

Output

输出文件中仅一行为一个整数,表示最高的满意度之和。


注意几个问题

  1. 什么时候更新答案?

    当前格子左边是\(1\),上边是\(2\)除去这个\(1\)和\(2\)后的状态上没有插头。

  2. 每次新一行的时候我们会把状态数组向右移动两位,这时候会当\(n\)比较大的时候出现负数,在插入\(Hash\)表取模后需要把\(Ta\)变成正数。

    当然也可以有其他的方法,用无符号整型自然溢出或者手动每次\(\&\)一个状态内全是\(1\),其余的位置全是\(0\)的数字。实测每次\(\&\)的速度是最快的,大概是其他两个的\(1/8\)。

    • 其实写的漂亮并不会出现负数
    • 但是一出现可能挂的很惨哦
  3. 在伸出插头时一定要注意边界,不能越过\(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\n",ans);
return 0;
}

2018.12.20