P3190 [HNOI2007] 神奇游乐园
题目描述
经历了一段艰辛的旅程后，主人公小 P 乘坐飞艇返回。在返回的途中，小 P 发现在漫无边际的沙漠中，有一块狭长的绿地特别显眼。往下仔细一看，才发现这是一个游乐场，专为旅途中疲惫的人设计。
娱乐场可以看成是一块大小为 n\times m 的区域，且这个 n\times m 的区域被分成 n\times m 个小格子，每个小格子中就有一个娱乐项目。
然而，小 P 并不喜欢其中的所有娱乐项目，于是，他给每个项目一个满意度。满意度为正时表示小 P 喜欢这个项目，值越大表示越喜欢。为负时表示他不喜欢，这个负数的绝对值越大表示他越不喜欢。为 0 时表示他对这个项目没有喜恶。
小 P 决定将飞艇停在某个小格中，然后每步他可以移动到相邻的上下左右四个格子的某个格子中。
小 P 希望找一条路径，从飞艇所在格出发，最后又回到这个格子。
小 P 有一个习惯，从不喜欢浪费时间。因此，他希望经过每个格子都是有意义的：他到一个地方后，就一定要感受以下那里的惊险和刺激，不管自己是不是喜欢那里的娱乐项目。而且，除了飞艇所在格，其他的格子他不愿意经过两次。小 P 希望自己至少要经过四个格子。
在满足这些条件的情况下，小 P 希望自己玩过的娱乐项目的满意度之和最高。你能帮他找到这个最高的满意度之和吗？
输入格式
第一行为两个正整数 n 和 m，表示游乐场的大小为 n\times m。
接下来的 n 行，每行有 m 个整数，第 (i + 1) 行的第 j 个数表示游乐场的第 i 行第 j 列的小格子中的娱乐项目的满意度 a_{i,j}。同一行的两个整数之间用空格隔开。
输出格式
仅一行为一个整数，表示最高的满意度之和。
输入输出样例 #1
输入 #1
4 4
100 300 -400 400
-100 1000 1000 1000
-100 -100 -100 -100
-100 -100 -100 1000
输出 #1
4000
说明/提示
数据规模与约定
对于 100\% 的数据，保证 2\leq n\leq 100，2\leq m\leq 6，-10^3\leq a_{i,j}\leq 10^3。
#include<bits/stdc++.h>
using namespace std;
int n,m,a[200][10],dp[2][40000],th[40000][110],idx;//dp用括号序列,四进制存三进制状态(因为四进制方便)
int erhui;
int s[100];
void check()//特判
{
int cnt=-1e9;
for(int i=1;i<n;i++)
{
for(int j=1;j<m;j++)
{
cnt=max(cnt,a[i][j]+a[i+1][j]+a[i][j+1]+a[i+1][j+1]);
}
}
if(cnt<0)
{
cout<<cnt;
erhui=1;
return;
}
}
int main()
{
cin>>n>>m;
int x,cnt,u;
for(int i=0;i<(1<<2*m+2);i++)//预处理,th[][100]存三进制合法状态,th[][x]存三进制状态中与第x位的插头匹配的插头
{
cnt=0,u=1;
for(int j=10;j>=0;j--)
{
x=(i>>2*j)&3;
if(x==3)
{
u=0;
break;
}
if(x<2)
{
cnt+=x;
continue;
}
if(cnt--==0)
{
u=0;
break;
}
}
if(u==1&&cnt==0)
{
cnt=0;
th[++idx][100]=i;
for(int j=10;j>=0;j--)
{
x=(i>>2*j)&3;
if(x==0)continue;
if(x==1)
{
s[++cnt]=2*j;
continue;
}
th[idx][2*j]=s[cnt];
th[idx][s[cnt]]=2*j;
cnt--;
}
}
}
memset(dp,-0x3f,sizeof dp);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
check();
if(erhui)
{
return 0;
}
dp[0][0]=0;
dp[0][6<<2*m-2]=a[1][1];
int xb=1,xb1,kk,c,op;
for(int i=1;i<=n;i++)//用当前位更新后续状态
{
for(int j=1;j<=m;j++)
{
if(i==n&&j==m)
{
break;
}
xb1=xb;
xb^=1;
memset(dp[xb1],-0x3f,sizeof dp[xb1]);
for(int id=1,k;id<=idx;id++)
{
k=th[id][100];
if(j!=m)
{
c=dp[xb][k]+a[i][j+1];
op=(k>>2*(m-j-1))&15;//当前位的操作符,如当前位为12时,操作符=1*4+2=6,当前位为10时,操作符=1*4+0=6,当前位为21时,操作符=2*4+1=9(四进制存三进制状态)
kk=(op<<2*(m-j-1))^k;//将当前位操作符的位置置0后的值(方便使用位运算给该位切换操作符)
if(op==0)//无插头
{
dp[xb1][kk]=max(dp[xb][k],dp[xb1][kk]);//下一位没插头
dp[xb1][kk^(6<<2*(m-j-1))]=max(c,dp[xb1][kk^(6<<2*(m-j-1))]);//下一位一个左插头,一个右插头
}
if(op==1||op==4)//一个=1的插头
{
dp[xb1][kk^(1<<2*(m-j-1))]=max(c,dp[xb1][kk^(1<<2*(m-j-1))]);//下方放一个=1的插头
dp[xb1][kk^(4<<2*(m-j-1))]=max(c,dp[xb1][kk^(4<<2*(m-j-1))]);//右侧放一个=1的插头
}
if(op==2||op==8)//一个=2的插头
{
dp[xb1][kk^(2<<2*(m-j-1))]=max(c,dp[xb1][kk^(2<<2*(m-j-1))]);//下方放一个=2的插头
dp[xb1][kk^(8<<2*(m-j-1))]=max(c,dp[xb1][kk^(8<<2*(m-j-1))]);//右侧放一个=2的插头
}
if(op==5)//当前位11
dp[xb1][kk^(3<<th[id][2*(m-j-1)])]=max(c,dp[xb1][kk^(3<<th[id][2*(m-j-1)])]);//合并,找到右插头匹配
if(op==10)//当前位22
dp[xb1][kk^(3<<th[id][2*(m-j)])]=max(c,dp[xb1][kk^(3<<th[id][2*(m-j)])]);//合并,找到左插头匹配
if(op==9)//当前位21
dp[xb1][kk]=max(c,dp[xb1][kk]);//直接合并,左右插头自动匹配
}
else
{
if(k&3)
{
continue;
}
c=dp[xb][k]+a[i+1][1];
op=(k>>2*m)&3;
kk=k^(op<<2*m);
kk>>=2;
if(op==0)
{
dp[xb1][kk]=max(dp[xb][k],dp[xb1][kk]);
dp[xb1][kk^(6<<2*m-2)]=max(c,dp[xb1][kk^(6<<2*m-2)]);
}
if(op==1)
{
dp[xb1][kk^(1<<2*m-2)]=max(c,dp[xb1][kk^(1<<2*m-2)]);
dp[xb1][kk^(4<<2*m-2)]=max(c,dp[xb1][kk^(4<<2*m-2)]);
}
if(op==2)
{
dp[xb1][kk^(2<<2*m-2)]=max(c,dp[xb1][kk^(2<<2*m-2)]);
dp[xb1][kk^(8<<2*m-2)]=max(c,dp[xb1][kk^(8<<2*m-2)]);
}
}
}
}
}
cout<<max(dp[xb][6]+a[n][m],dp[xb][0]);//可以没有插头,或者一个左插头,一个右插头
}