题意：给出一个数表，规定取出一个数后周围的八个数都不可取，求可获得的最大数字和

思路：状态压缩dp，每一行的取数方法为状态，显然，由于取数规则的限制，可取的状态并不是

1<<size_col，而是非常有限的，我们可以预处理出状态(不超过1600个)，大大降低时间复杂度，

 

运行时间：140ms

#include <bits/stdc++.h>

using namespace std;

int dp[][],sta[],len,n;

int g[][];

void init()

{

    for(int i=;i<(<<);i++)if(!(i&(i<<))&&!(i&(i>>)))sta[len++]=i;//预处理出所有可取状态

}

int Res[][];//加个记忆化，避免重复的计算

inline int calstatus(int row,int sta,int j)//计算出row行这个状态所有数字的的sum

{

    if(Res[row][j])

        return Res[row][j];

    int res=;

    for(int j=;j<n;j++){

        if(sta&)

        {

            res+=g[row][j];

        }

        sta>>=;

    }

    return Res[row][j]=res;

}

int main()

{

    init();

    while (n=,~scanf("%d",&g[][n++]))

    {

        memset(Res,,sizeof(Res));

        memset(dp,, sizeof(dp));//初始化

        //坑爹输入部分

        while (true)

        {

            scanf("%d",&g[][n++]);

            if(getchar()=='\n')break;

        }

        for(int i=;i<n;i++)

            for(int j=;j<n;j++)scanf("%d",&g[i][j]);

        //第一行预处理

        for(int i=;i<n;i++)

            for(int j=;j<len&&sta[j]<(<<n);j++)dp[][j]=calstatus(,sta[j],j);

        int ans=;

        for(int i=;i<n;i++)

        {

            for(int j=;j<len&&sta[j]<(<<n);j++)

            {

                for(int k=;k<len&&sta[k]<(<<n);k++)

                    if(!(sta[k]&(sta[j]<<))&&!(sta[k]&(sta[j]>>))&&!(sta[k]&sta[j])){//左移右移与不移，两个状态都不冲突，进行状态转移

                        dp[i][k]=max(dp[i][k],dp[i-][j]+calstatus(i,sta[k],k));

                        ans=max(ans,dp[i][k]);

                    }

            }

        }

        printf("%d\n",ans);

    }

    return ;

}