题解：
简单的插头dp
加上一个代价即可
代码：
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; const int N=15,HASH=10007,STATE=1000100,M=1e9+7; typedef long long ll; int n,m,ch[N],code[N],mp[N][N],mp2[N][N]; struct HASHMAP { int head[HASH],next[STATE],size; ll state[STATE],f[STATE]; void init() { size=0; memset(head,-1,sizeof(head)); } void push(ll st,ll ans) { int h=st%HASH; for (int i=head[h];i!=-1;i=next[i]) if (state[i]==st) { f[i]=max(ans,f[i]); return; } state[size]=st; f[size]=ans; next[size]=head[h]; head[h]=size++; } }hm[2]; void decode(ll st) { for (int i=m;i>=0;i--) { code[i]=st&7; st>>=3; } } ll encode() { int cnt=1; ll st=0; memset(ch,-1,sizeof(ch)); ch[0]=0;ch[7]=7; for (int i=0;i<=m;i++) { if (ch[code[i]]==-1)ch[code[i]]=cnt++; code[i]=ch[code[i]]; st<<=3; st|=code[i]; } return st; } void shift() { for (int i=m;i;i--)code[i]=code[i-1]; code[0]=0; } void dp(int r,int c,int cur) { for (int k=0;k<hm[cur].size;k++) { decode(hm[cur].state[k]); int up=code[c],left=code[c-1]; if ((r==1&&c==1)||(r==n&&c==m)) { if (!up&&!left) { if (c<m) { code[c]=7; code[c-1]=0; hm[cur^1].push(encode(),hm[cur].f[k]+mp[r][c]); } if (r<n) { code[c]=0; code[c-1]=7; if (m==c)shift(); hm[cur^1].push(encode(),hm[cur].f[k]+mp[r][c]); } } if (up||left) { code[c]=code[c-1]=0; if (m==c)shift(); hm[cur^1].push(encode(),hm[cur].f[k]+mp[r][c]); } continue; } if (up&&left) { if (up!=left) { int t=max(up,left); code[c]=code[c-1]=0; for (int i=0;i<=m;i++) if (code[i]==left||code[i]==up)code[i] = t; if (m==c) shift(); hm[cur^1].push(encode(),hm[cur].f[k]+mp[r][c]); } } else if (up||left) { if (c<m) { code[c-1]=0; code[c]=up|left; if (m==c)shift(); hm[cur^1].push(encode(),hm[cur].f[k]+mp[r][c]); } if (r<n) { code[c-1]=up|left; code[c]=0; if (m==c) shift(); hm[cur^1].push(encode(),hm[cur].f[k]+mp[r][c]); } } else { if (c<m&&r<n) { code[c-1]=code[c]=6; hm[cur^1].push(encode(),hm[cur].f[k]+mp[r][c]); } code[c]=code[c-1]=0; if (c==m) shift(); hm[cur^1].push(encode(),hm[cur].f[k]); } } } int main() { int cas=0; while (~scanf("%d%d",&n,&m)) { for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)scanf("%d", &mp[i][j]); if (n==1&&m==1) { printf("Case %d: %d ",++cas,mp[1][1]); continue; } if (n<m) { for (int i=1;i<=m;i++) for (int j=1;j<=n;j++)mp2[i][j]=mp[j][i]; for (int i=1;i<=m;i++) for (int j=1;j<=n;j++)mp[i][j]=mp2[i][j]; swap(n,m); } int cur=0; hm[cur].init(); hm[cur].push(0,0); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { hm[cur^1].init(); dp(i,j,cur); cur^=1; } ll ans=-1e18; for (int i=0;i<hm[cur].size;i++)ans=max(ans,hm[cur].f[i]); printf("Case %d: %lld ",++cas,ans); } return 0; }