题意：给出一个数表，规定取出一个数后周围的八个数都不可取，求可获得的最大数字和
思路：状态压缩dp，每一行的取数方法为状态，显然，由于取数规则的限制，可取的状态并不是
1<<size_col，而是非常有限的，我们可以预处理出状态(不超过1600个)，大大降低时间复杂度，
运行时间：140ms
#include <bits/stdc++.h> using namespace std; int dp[16][1600],sta[1600],len,n; int g[15][15]; void init() { for(int i=0;i<(1<<15);i++)if(!(i&(i<<1))&&!(i&(i>>1)))sta[len++]=i;//预处理出所有可取状态 } int Res[16][1600];//加个记忆化，避免重复的计算 inline int calstatus(int row,int sta,int j)//计算出row行这个状态所有数字的的sum { if(Res[row][j]) return Res[row][j]; int res=0; for(int j=0;j<n;j++){ if(sta&1) { res+=g[row][j]; } sta>>=1; } return Res[row][j]=res; } int main() { init(); while (n=0,~scanf("%d",&g[0][n++])) { memset(Res,0,sizeof(Res)); memset(dp,0, sizeof(dp));//初始化 //坑爹输入部分 while (true) { scanf("%d",&g[0][n++]); if(getchar()=='\n')break; } for(int i=1;i<n;i++) for(int j=0;j<n;j++)scanf("%d",&g[i][j]); //第一行预处理 for(int i=0;i<n;i++) for(int j=0;j<len&&sta[j]<(1<<n);j++)dp[0][j]=calstatus(0,sta[j],j); int ans=0; for(int i=1;i<n;i++) { for(int j=0;j<len&&sta[j]<(1<<n);j++) { for(int k=0;k<len&&sta[k]<(1<<n);k++) if(!(sta[k]&(sta[j]<<1))&&!(sta[k]&(sta[j]>>1))&&!(sta[k]&sta[j])){//左移右移与不移，两个状态都不冲突，进行状态转移 dp[i][k]=max(dp[i][k],dp[i-1][j]+calstatus(i,sta[k],k)); ans=max(ans,dp[i][k]); } } } printf("%d\n",ans); } return 0; }