来自FallDream的博客，未经允许，请勿转载，谢谢。
给定一个方阵，你要取出一些数字，满足没有两个格子八联通相邻的前提下和最大，求这个和
n<=15
插头dp，保存轮廓线以及目前转移点左上方那个格子的状态，枚举格子转移即可。
#include<iostream> #include<cstdio> #include<cstring> #define MN 15 using namespace std; inline int read() {int x = 0 , f = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f; }char st[5000]; int a[MN+5][MN+5],m,f[2][1<<16];int Strread() {int top=0,j=0;for(int i=0;st[i]==' '||(st[i]>='0'&&st[i]<='9');++i)if(st[i]==' ') a[1][++top]=j,j=0;else j=j*10+st[i]-'0';return a[1][++top]=j,top; } inline void R(int&x,int y){y>x?x=y:0;} int main() {while(cin.getline(st,5000)){m=Strread();if(m==1&&a[1][1]==0) continue;for(int i=2;i<=m;++i)for(int j=1;j<=m;++j)a[i][j]=read();memset(f,0,sizeof(f));int now=1,pre=0;for(int i=1;i<=m;++i)for(int j=1;j<=m;++j,swap(now,pre),memset(f[now],0,sizeof(f[now])))for(int k=0;k<1<<(m+1);++k){R(f[now][(k&((1<<m)-(1<<(j-1))-1))|((k&(1<<(j-1)))?(1<<m):0)],f[pre][k]);if((j==1||(!((k&(1<<m)))&&!(k&(1<<(j-2)))))&&!(k&(1<<(j-1)))&&(j==m||!(k&(1<<j))))R(f[now][(k&((1<<m)-1))|(1<<(j-1))|((k&(1<<(j-1)))?(1<<m):0)],f[pre][k]+a[i][j]);}int ans=0;for(int i=0;i<1<<(m+1);++i) ans=max(ans,f[pre][i]);cout<<ans<<endl;}return 0; }
