题意：有一个n*m的矩阵，每个格子中有一个值（可能负值），要从左上角走到右下角，求路径的最大花费。
思路：
除了起点和终点外，其他的点可以走，也可以不走。
（2）我用的是括号表示法，所以起始状态为')'，即仅有一个右括号，那么到右下角也应该是只有一个右括号。因为，如果碰到()),加粗表示起点的那个右括号,那么合并后变成)##，仍然是右括号，如果是)()，那么合并后变成##)，仍然是右括号，相当于延续了。插头每到达一个格子就先将其值给加上，如果要合并的时候，再减掉（因为多算了一次），因此，新括号的出现，就需要多加上3个格子的值了。
（2）还有一个更直观的办法，就是添加半个圈，从起点到终点，设他们都为必走的格子，那就跟FZU 1977 PANDORA ADVENTURE （插头DP，常规）差不多了，只是没有了障碍格子而已。
比如矩阵：
000
000
000
可以建图为（其中b为必走的格子）：
bbbb
b00b
000b
00bb
由于不用这样建图也是很容易解决的，所以下面代码就不这样建图了。
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int N=;
int g[N][N], cur, n, m;
struct Hash_Map
{
static const int mod=;
static const int NN=;
int head[mod]; //桶指针
int next[NN]; //记录链的信息
LL status[NN]; //状态
LL value[NN]; //状态对应的DP值。
int size; void clear() //清除哈希表中的状态
{
memset(head, -, sizeof(head));
size = ;
} void insert(LL st, LL val) //插入状态st的值为val
{
int h = st%mod;
for(int i=head[h]; i!=-; i=next[i])
{
if(status[i] == st) //这个状态已经存在，累加进去。
{
value[i] = max(value[i], val);
return ;
}
} status[size]= st; //找不到状态st，则插入st。
value[size] = val;
next[size] = head[h] ; //新插入的元素在队头
head[h] = size++;
}
}hashmap[]; inline int getbit(LL s,int pos) //取出状态s的第pos个插头
{
return (s>>*pos)&;
}
inline int setbit(LL s,int pos,int bit) //将状态s的第pos个插头设置为bit
{
if(s&(<<*pos )) s^=<<(*pos);
if(s&(<<(*pos+))) s^=<<(*pos+);
return (s|(bit<<*pos));
} int Fr(LL s,int pos,int bit) //寻找状态s的第pos个插头对应的右括号。
{
int cnt=;
for(pos+=; pos<m; pos++)
{
if(getbit(s, pos)==-bit) cnt++;
if(getbit(s, pos)==bit) cnt--;
if(cnt==-) return setbit(s, pos, -bit);
}
}
int Fl(LL s,int pos,int bit) //寻找状态s的第pos个插头对应的左括号。
{
int cnt=;
for(pos--; pos>=; pos--)
{
if(getbit(s, pos)==-bit) cnt++;
if(getbit(s, pos)==bit) cnt--;
if( cnt==-) return setbit(s, pos, -bit);
}
}
LL ans;
void DP(int i,int j)
{
for(int k=; k<hashmap[cur^].size; k++)
{
LL s=hashmap[cur^].status[k];
LL v=hashmap[cur^].value[k];
int R=getbit(s, j), D=getbit(s, j+);
LL t=(setbit(s,j,)&setbit(s,j+,));
if(R && D) //两个括号
{ if(R==D) //同个方向的括号
{
if(R==) t=Fr(t, j, ); //要改
else t=Fl(t, j, );
hashmap[cur].insert(t, v-g[i][j]);
}
else if( R== && D== ) //不同的连通分量
hashmap[cur].insert(t, v-g[i][j]);
}
else if(R || D) //仅1个括号
{
if( i+==n && j+==m && t== && ( R== || D== ) ) //终点才能闭合
ans=max(ans, v);
if(R) //右插头
{
if(i+<n ) hashmap[cur].insert(s, v+g[i+][j]);//往下
if(j+<m ) hashmap[cur].insert(setbit(t,j+,R), v+g[i][j+]);//往右
}
else //下插头
{
if(j+<m ) hashmap[cur].insert(s, v+g[i][j+]); //往右
if(i+<n ) hashmap[cur].insert(setbit(t,j,D), v+g[i+][j]);//往下
}
}
else
{
if( i+j ) hashmap[cur].insert(s, v); //不装括号
if( j+<m && i+<n && i+j ) //新括号
hashmap[cur].insert( setbit(s,j,)|setbit(s,j+,), v+g[i][j]+g[i+][j]+g[i][j+]);
}
}
} void cal()
{
for(int i=; i<n; i++)
{
cur^=;
hashmap[cur].clear();
for(int j=; j<hashmap[cur^].size; j++) //新行，需要左移一下状态。
hashmap[cur].insert( hashmap[cur^].status[j]<<, hashmap[cur^].value[j] );
for(int j=; j<m; j++)
{
cur^=;
hashmap[cur].clear();
DP(i,j);
}
}
} int main()
{
//freopen("input.txt", "r", stdin);
int Case=;
while(~scanf("%d%d",&n,&m))
{
memset(g, , sizeof(g));
ans=-INF; //注意
cur=;
for(int i=; i<n; i++) //输入
for(int j=; j<m; j++)
scanf("%d",&g[i][j]); hashmap[cur].clear();
hashmap[cur].insert(, g[][]);
cal();
printf("Case %d: %lld\n", ++Case, ans);
}
return ;
}
AC代码