题目大意：有个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;}

HDU 2167 Pebbles