2 2 1 2 3 1 3 3 0 -20 100 1 -20 -20 1 1 1
Case 1: 5 Case 2: 61
首先初始化状态即[1,0]的状态为1,表示从[1,0] => [1,1]有一个插头，这样就能保证是从点[1,1]开始 然后将点[n+1,m]表示为可经过，然后进行插头DP时从[n,m] => [n+1,m]可以有插头，所以最终也保证了以点[n,m]结束 在这个过程中进行插头DP只需要去掉p=1,q=2的情况就行，因为这样会形成环 另外还有一种方法是增加外围使得题目变成求回路的最值 0 0 0 0 0 0 # # # 0 ------ 1 0 1 |# 0 1 1 1 |# 0 ------ # # 0 0 0 这样增加外围就一定能保证求的回路是如果去掉外围就是从点[1,1]到[n,m]
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <iomanip>
#define INF 99999999
typedef long long LL;
using namespace std;
const int MAX=30000+10;
const int N=10+10;
int n,m,size,index;
int val[N][N],total[2],bit[N];
int head[MAX],next[MAX],Hash[MAX];
LL dp[2][MAX],state[2][MAX],sum;
void HashCalState(LL s,LL Val){
int pos=s%MAX;
for(int i=head[pos];i != -1;i=next[i]){
if(state[index][Hash[i]] == s){
dp[index][Hash[i]]=max(dp[index][Hash[i]],Val);
return;
}
}
++total[index];
state[index][total[index]]=s;
dp[index][total[index]]=Val;
//头插法
Hash[size]=total[index];
next[size]=head[pos];
head[pos]=size++;
}
void DP(){
index=0;
total[index]=1;
state[index][1]=1;//初始化的状态是第一格有一个插头进来(从0进来)
dp[index][1]=val[1][1];
sum=-INF;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
memset(head,-1,sizeof head);
size=0;
index=index^1;
total[index]=0;
for(int k=1;k<=total[index^1];++k){
LL s=state[index^1][k];
LL Val=dp[index^1][k];
int p=(s>>bit[j-1])%4;
int q=(s>>bit[j])%4;
int d=(s>>bit[j+1])%4;
if(!p && !q){
HashCalState(s,Val);//跳过该格不经过(这里可以不用加判断if(i != n || j != m),因为n-1,m一定会经过n,m)
if(val[i][j+1] == INF || val[i+1][j] == INF)continue;
s=s+(1<<bit[j-1])+2*(1<<bit[j]);
if(!d)HashCalState(s,Val+val[i+1][j]+val[i][j+1]+val[i][j]);//注意这里一定还要加上val[i][j]
else HashCalState(s,Val+val[i+1][j]+val[i][j]);//如果i,j+1已经由上面一行到达则不能重复累加该点价值
}else if(!p && q){
if(val[i][j+1] != INF){
//if(!d)Val=Val+val[i][j+1];//这里不能这样改变Val,因为会影响下一个if里面的Val
if(!d)HashCalState(s,Val+val[i][j+1]);
else HashCalState(s,Val);//如果i,j+1已经由上面一行到达则不能重复累加该点价值
}
if(val[i+1][j] != INF){
s=s+q*(1<<bit[j-1])-q*(1<<bit[j]);
Val=Val+val[i+1][j];
HashCalState(s,Val);
}
}else if(p && !q){
if(val[i+1][j] != INF)HashCalState(s,Val+val[i+1][j]);
if(val[i][j+1] != INF){
s=s-p*(1<<bit[j-1])+p*(1<<bit[j]);
if(!d)HashCalState(s,Val+val[i][j+1]);
else HashCalState(s,Val);//如果i,j+1已经由上面一行到达则不能重复累加该点价值
}
}else if(p == 1 && q == 1){
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])-2*(1<<bit[t]);
break;
}
}
s=s-(1<<bit[j-1])-(1<<bit[j]);
HashCalState(s,Val);
}else if(p == 2 && q == 2){
int b=1;
for(int t=j-2;t>=0;--t){
int v=(s>>bit[t])%4;
if(v == 2)++b;
if(v == 1)--b;
if(!b){
s=s-(1<<bit[t])+2*(1<<bit[t]);
break;
}
}
s=s-2*(1<<bit[j-1])-2*(1<<bit[j]);
HashCalState(s,Val);
}else if(p == 2 && q == 1){
s=s-2*(1<<bit[j-1])-(1<<bit[j]);
HashCalState(s,Val);
}
}
}
for(int k=1;k<=total[index];++k)state[index][k]<<=2;
}
sum=dp[index][1];//for(int k=1;k<=total[index];++k)sum=max(sum,dp[index][k]);//这里可以不用for，因为最后到达n,m->n+1,m状态只有一种
}
int main(){
int num=0;
for(int i=0;i<N;++i)bit[i]=i<<1;
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<N;++i)for(int j=1;j<N;++j)val[i][j]=INF;//这里i<=N,j<=N会覆盖bit的内存地址,教训啊
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)scanf("%d",&val[i][j]);
}
val[n+1][m]=0;//在最后一个下面添加一个虚拟格子可以经过，则插头dp后的路线一定是以最后一格结尾
DP();
printf("Case %d: %lld\n",++num,sum);
}
return 0;
}
/*
7 8
1 1 1 1 1 1 1 1
-1 -1 -1 -1 -1 -1 -1 1
1 1 1 -1 -1 -1 -1 1
1 -1 1 -1 -1 -1 -1 1
1 -1 1 1 1 1 1 1
1 -1 -1 -1 -1 -1 -1 -1
1 1 1 1 1 1 1 1
*/hdu3377之简单路径求最值,布布扣,bubuko.com
原文：http://blog.csdn.net/xingyeyongheng/article/details/24499375