题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3377
简单路径要求权值最大，那么为了回避括号序列单独插头的情况特判多，考虑使用最小表示法。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 21
#define inf ((0x7fffffff)-1)
#define llg int
#define sizee 233
#define maxnZT ((1<<20)+1)
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,m,code[maxn],zt[][maxnZT],v[][maxnZT],g[][],size[],now,ne,ans=inf*-;
llg maze[][],val[][],ch[];
void outcode(llg x){for (llg i=;i<=m;i++) code[i]=x&,x>>=;} struct node
{
llg x,val,pos;
}; vector<node>a[][sizee]; void decode(llg x) {for (llg i=;i<=m;i++) code[i]=x&,x>>=;} void encode(llg p,llg val)
{
for (llg i=;i<=;i++) ch[i]=-;
ch[]=;
llg C=;
for (llg i=;i<=m;i++)
{
if (ch[code[i]]==-) ch[code[i]]=++C;
code[i]=ch[code[i]];
}
llg x=;
for (llg i=;i<=m;i++) x+=code[i]*(<<(i*));
llg wz=x%sizee,E=a[p][wz].size();
for (llg i=;i<E;i++)
if (a[p][wz][i].x==x)
{
a[p][wz][i].val=max(a[p][wz][i].val,val);
v[p][a[p][wz][i].pos]=max(v[p][a[p][wz][i].pos],val);
return ;
}
size[p]++;
node NEW; NEW.x=x; NEW.val=val; NEW.pos=size[p];
a[p][wz].push_back(NEW);
zt[p][size[p]]=x; v[p][size[p]]=val;
} void init_a(llg p){for (llg i=;i<sizee;i++) a[p][i].clear(); size[p]=;} void shift()///换行 移位
{
for(int i=m;i>;i--)
code[i]=code[i-];
code[]=;
} void dp(llg x,llg y)
{
llg left,up,V;
for (llg K=;K<=size[now];K++)
{
decode(zt[now][K]);
left=code[y-],up=code[y];//左上插头
V=v[now][K];
//------------------------------------------------------------
if ((x== && y==))//开始位置
{
if (maze[x][y+])//往左走
{
code[y]=,code[y-]=;
encode(ne,V+val[x][y]);
}
if (maze[x+][y])//往下走
{
code[y-]=,code[y]=;
encode(ne,V+val[x][y]);
}
continue;
}
//------------------------------------------------------------
if (x==n && y==m)//结束位置
{
if ((!left && up) || (left && !up))//必须有且仅有一个插头
{
code[y]=code[y-]=;
bool pd=true;
for (llg t=;t<=m;t++) if (code[t]) pd=false;
if (pd) ans=max(ans,V+val[x][y]);
}
continue;
}
//------------------------------------------------------------
if (left && up)//插头合并
{
if (left!=up)//如果属于同一个连通块则非法(因为形成了环)
{
code[y]=code[y-]=;
for (llg t=;t<=m;t++) if (code[t]==up) code[t]=left;
if (y==m) shift();
encode(ne,V+val[x][y]);
}
continue;
}
//------------------------------------------------------------
if (left || up)//延续原来的连通分量
{
llg tmp;
if (left) tmp=left;else tmp=up;
if (maze[x][y+])
{
code[y-]=,code[y]=tmp;
encode(ne,V+val[x][y]);
}
if (maze[x+][y])
{
code[y-]=tmp,code[y]=;
if (y==m) shift();
encode(ne,V+val[x][y]);
}
}
//------------------------------------------------------------
if (!left && !up)//没有插头，新建连通分量或者不走这一个格子
{
if (maze[x][y+] && maze[x+][y])
{
code[y]=code[y-]=;
encode(ne,V+val[x][y]);
}
code[y]=code[y-]=;
if (y==m) shift();
encode(ne,V);
}
}
} void work()
{
now=,ne=;
encode(now,);
for (llg i=;i<=n;i++)
{
for (llg j=;j<=m;j++)
{
ne=now^;
init_a(ne);
dp(i,j);
now=ne;
}
}
} void init()
{
memset(maze,,sizeof(maze));
for (llg i=;i<=n;i++)
for (llg j=;j<=m;j++)
scanf("%d",&val[i][j]),maze[i][j]=;
} int main()
{
yyj("hdu3377");
llg cas=;
while (scanf("%d%d",&n,&m)!=EOF)
{
ans=inf*-;
cas++;
init();
if (n== && m==)
{
printf("Case %d: %d\n",cas,val[n][m]);
init_a(),init_a();
continue;
}
work();
printf("Case %d: %d\n",cas,ans);
init_a(),init_a();
}
return ;
}