题目大意：有个N*N( 3<=N<=15 )方阵, 可从中若干个数, 使其总和最大.取数要求, 当某一个数被选, 其周围8个数都不能选.
题解：记s数组为合法状态，即没有相邻的数字同时被选的二进制数，sum[i][j]表示第i行j状态下数字总和，那么Dp时只要枚举上一行的状态，判断是否可行，就可以转移出这一行每种合法状态的最优解。
#include <cstdio>
#include <cstring>
#include <algotithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int t,i,n,m,k,dp[16][1<<16],a[16][16],sum[16][1<<16],s[1<<16],ans;
int main(){
char str[112];
while(gets(str)){
int len=strlen(str);n=0;
for(int i=0;i<len;i+=3)a[0][n++]=(str[i]-'0')*10+(str[i+1]-'0');
for(i=1;i<n;i++){
t=0,gets(str);
for(int j=0;j<len;j+=3)a[i][t++]=(str[j]-'0')*10+(str[j+1]-'0');
}
for(i=m=0;i<(1<<n);i++)if((i&(i<<1))==0)s[m++]=i;
memset(sum,0,sizeof(sum));memset(dp,0,sizeof(dp));
rep(i,n)rep(j,m)rep(k,n)if(s[j]&(1<<k))sum[i][j]+=a[i][k];
rep(i,m)dp[0][i]=sum[0][i];
for(int i=1;i<n;i++)rep(j,m)rep(k,m){
if(s[j]&s[k])continue;
if(s[j]&(s[k]>>1))continue;
if(s[j]&(s[k]<<1))continue;
dp[i][j]=max(dp[i][j],dp[i-1][k]+sum[i][j]);
}ans=0;
rep(i,m)ans=max(ans,dp[n-1][i]);
printf("%d\n",ans);gets(str);
}return 0;
}