#题目描述
经历了一段艰辛的旅程后,主人公小P乘坐飞艇返回。在返回的途中,小P发现在漫无边际的沙漠中,有一块狭长的绿地特别显眼。往下仔细一看,才发现这是一个游乐场,专为旅途中疲惫的人设计。娱乐场可以看成是一块大小为n×m的区域,且这个n×m的区域被分成n×m个小格子,每个小格子中就有一个娱乐项目。然而,小P并不喜欢其中的所有娱乐项目,于是,他给每个项目一个满意度。满意度为正时表示小P喜欢这个项目,值越大表示越喜欢。为负时表示他不喜欢,这个负数的绝对值越大表示他越不喜欢。为0时表示他对这个项目没有喜恶。小P决定将飞艇停在某个小格中,然后每步他可以移动到相邻的上下左右四个格子的某个格子中。小P希望找一条路径,从飞艇所在格出发,最后又回到这个格子。小P有一个习惯,从不喜欢浪费时间。因此,他希望经过每个格子都是有意义的:他到一个地方后,就一定要感受以下那里的惊险和刺激,不管自己是不是喜欢那里的娱乐项目。而且,除了飞艇所在格,其他的格子他不愿意经过两次。小P希望自己至少要经过四个格子。 在满足这些条件的情况下,小P希望自己玩过的娱乐项目的满意度之和最高。你能帮他找到这个最高的满意度之和吗?
#做法
我们用括号序列来表示,第一位表示左插头的状态,第二位表示上插头的状态
0 0
(# #
) -> 1 2
(( )
)/0 0
(# #
)
2 1
(( )
) -> 0 0
(# #
)
1 1
(( (
) -> 0 0
(# #
)
2 2
() )
) -> 0 0
(# #
)
1 2
() )
) -> 0 0
(# #
)
这种状态相当于将这个回路“封口”,所以要更新答案
1/2 0
((/) #
) -> 1/2 0
((/) #
) / 0 1/2
(# (/)
)
0 1/2
((/) #
) -> 1/2 0
((/) #
) / 0 1/2
(# (/)
)
#AC Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1005,maxm=8,maxQ=(1<<(maxm*2));
struct qNode{
int val,stt;
qNode(){}
qNode(const int &v,const int &s):
val(v),stt(s){}
}que[2][maxQ];
int qT[2],now=0;
int n,m,j,Map[maxn][maxm];
int pos[2][maxQ];
inline int getStt(const int &stt,const int &pos){return ((stt>>(pos*2))&3);}
inline int setStt(const int &stt,const int &pos,const int &stt2)
{return stt+((-getStt(stt,pos)+stt2)<<(2*pos));}
void pushQueue(const int &stt,const int &val)
{
if (j==m-1 && getStt(stt,m))
return;
int &p=pos[now][stt];
if (p)
que[now][p].val=max(que[now][p].val,val);
else
que[now][p=++qT[now]]=qNode(val,stt);
}
int change1(const int &stt,int i)
{
for (int stack=0;i<m;i++)
{
const int tmp=getStt(stt,i);
if (tmp==1)
++stack;
else if (tmp==2)
--stack;
if (!stack)
return setStt(stt,i,1);
}
return -1;
}
int change2(const int &stt,int i)
{
for (int stack=0;i>=0;i--)
{
const int tmp=getStt(stt,i);
if (tmp==1)
--stack;
else if (tmp==2)
++stack;
if (!stack)
return setStt(stt,i,2);
}
return -1;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
scanf("%d",&Map[i][j]);
pushQueue(0,0);
now^=1;
int ans=0x80000000;
for (int i=0;i<n;i++)
for (j=0;j<m;j++)
{
for (int p=1,t=qT[now^1];p<=t;p++)
{
const int stt=que[now^1][p].stt;
const int val=que[now^1][p].val;
const int up=getStt(stt,j),le=getStt(stt,m);
if (up==0 && le==0)
pushQueue(setStt(setStt(stt,j,1),m,2),val+Map[i][j]),
pushQueue(stt,val);
else if (up==1 && le==2)
pushQueue(setStt(setStt(stt,j,0),m,0),val+Map[i][j]);
else if (up==0 || le==0)
pushQueue(setStt(setStt(stt,j,0),m,up+le),val+Map[i][j]),
pushQueue(setStt(setStt(stt,m,0),j,up+le),val+Map[i][j]);
else if (up==1 && le==1)
pushQueue(setStt(setStt(change1(stt,j),j,0),m,0),val+Map[i][j]);
else if (up==2 && le==2)
pushQueue(setStt(setStt(change2(stt,j),j,0),m,0),val+Map[i][j]);
else if (up==2 && le==1)
if (setStt(setStt(stt,j,0),m,0)==0)
ans=max(ans,val+Map[i][j]);
}
now^=1;
for (int h=1;h<=qT[now];++h)
pos[now][que[now][h].stt]=0;
qT[now]=0;
}
printf("%d\n",ans);
return 0;
}