【BZOJ 1187】 [HNOI2007]神奇游乐园

1187: [HNOI2007]神奇游乐园

Time Limit: 10 Sec Memory Limit: 162 MB Submit: 706 Solved: 358 [Submit][Status][Discuss] Description

经历了一段艰辛的旅程后，主人公小P乘坐飞艇返回。在返回的途中，小P发现在漫无边际的沙漠中，有一块狭长的绿地特别显眼。往下仔细一看，才发现这是一个游乐场，专为旅途中疲惫的人设计。娱乐场可以看成是一块大小为n×m的区域，且这个n×m的区域被分成n×m个小格子，每个小格子中就有一个娱乐项目。然而，小P并不喜欢其中的所有娱乐项目，于是，他给每个项目一个满意度。满意度为正时表示小P喜欢这个项目，值越大表示越喜欢。为负时表示他不喜欢，这个负数的绝对值越大表示他越不喜欢。为0时表示他对这个项目没有喜恶。小P决定将飞艇停在某个小格中，然后每步他可以移动到相邻的上下左右四个格子的某个格子中。小P希望找一条路径，，从飞艇所在格出发，最后又回到这个格子。小P有一个习惯，从不喜欢浪费时间。因此，他希望经过每个格子都是有意义的：他到一个地方后，就一定要感受以下那里的惊险和刺激，不管自己是不是喜欢那里的娱乐项目。而且，除了飞艇所在格，其他的格子他不愿意经过两次。小P希望自己至少要经过四个格子。在满足这些条件的情况下，小P希望自己玩过的娱乐项目的满意度之和最高。你能帮他找到这个最高的满意度之和吗？

Input

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

Output

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

Sample Input

4 4

100 300 -400 400

-100 1000 1000 1000

-100 -100 -100 -100

-100 -100 -100 1000 Sample Output

4000 HINT

大家测下这个数据 5 5 1 1 -100 3 3 1 1 -100 3 3 1 1 -100 3 3 1 1 -100 3 3 1 1 -100 3 3 结果是30?

插头dp。

模板化的转移。

出解的情况就是当前格子的插头为()，且整个轮廓线上没有别的插头。（因为如果别的地方还有插头的话，必然会在后面几行中出现()插头的情况，就会多算了）

用哈希表来存四进制的状态，可以加速代码。

;int tot=0,state[2][105],a[205][205],h[505],f[2][105],total[2],now,pre,n,m;int bit[20];struct edge{int ne;}e[105];void Solve(int s,int num){int x=s%mod;for (int i=h[x];i;i=e[i].ne)if (state[now][i]==s){if (num>f[now][i])f[now][i]=num;return;}tot++;state[now][tot]=s;f[now][tot]=num;e[tot].ne=h[x];h[x]=tot;}void Plugdp(){now=0;state[now][1]=0;total[now]=1;f[now][1]=0;int ans=-inf;for (int i=1;i<=n;i++){for (int j=1;j<=total[now];j++)state[now][j]<<=2;for (int j=1;j<=m;j++){tot=0;memset(h,0,sizeof(h));pre=now,now=pre^1;total[now]=0;memset(f[now],-127,sizeof(f[now]));for (int k=1;k<=total[pre];k++){int s=state[pre][k];int num=a[i][j]+f[pre][k];int p=(s>>bit[j-1])%4,q=(s>>bit[j])%4;if (p+q==0){Solve(s,num-a[i][j]);if (j!=m)Solve(s+(1<<bit[j-1])+2*(1<<bit[j]),num);}else if (!p&&q){if (j!=m)Solve(s,num);Solve(s-q*(1<<bit[j])+q*(1<<bit[j-1]),num);}else if (p&&!q){Solve(s,num);if (j!=m)Solve(s-p*(1<<bit[j-1])+p*(1<<bit[j]),num);}else if (p+q==2){int b=1;for (int t=j+1;t<=m;t++){int v=(s>>bit[t])%4;if (v==1) b++;if (v==2) b–;if (!b){s=s-(1<<bit[t]);break;}}Solve(s-(1<<bit[j-1])-(1<<bit[j]),num);}else if (p+q==4){int b=-1;for (int t=j-2;t>=0;t–){int v=(s>>bit[t])%4;if (v==1) b++;if (v==2) b–;if (!b){s=s+(1<<bit[t]);break;}}Solve(s-2*(1<<bit[j-1])-2*(1<<bit[j]),num);}else if (p==1&&q==2){if (s==(p<<bit[j-1])+(q<<bit[j])&&ans<num)ans=num;}else if (p==2&&q==1){Solve(s-2*(1<<bit[j-1])-(1<<bit[j]),num);}}total[now]=tot;}}printf(“%d\n”,ans);}int main(){scanf(“%d%d”,&n,&m);for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)scanf(“%d”,&a[i][j]);for (int i=0;i<=15;i++)bit[i]=i<<1;Plugdp();return 0;}

感悟： 1.RE是因为在一行的最后一个还继续添加__+这样的插头，下一行处理的时候直接<<2，导致最后状态过大。

2.一直提交，发现一个轮廓线的有效状态只有不超过105个。。

带上心灵去旅行，以平和的心态看待一切，