【题意】给定一个N*N的方格，让你在里面取出一些数使其和最大，要求每一个数不能与其相邻的8个数同时取出

【解题方法】状压DP。dp[i][j]表示第i行状态为j可以得到的最大取值，转移易得为dp[i][j] = max(dp[i][j], dp[i-1][k] + sum[i][j])。

【期望复杂度】O(1579*n*1579)

【代码君】别忘了这坑爹的getchar。。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int dp[22][40000];
int sum[22][40000];//合法状态的数和
int s[40000];//合法的状态被保存在这里
int a[22][22], b[22], n, m;
char str[110];

int main()
{
    b[0] = 1;
    for(int i = 1; i < 16; i++) b[i] = b[i-1] * 2;
    while(gets(str)){
        int le = strlen(str);
        n = 0;
        for(int i = 0; i < le; i += 3){
            a[0][n++] = (str[i] - '0') * 10 + (str[i+1] - '0');
        }
        for(int i = 1; i < n; i++){
            m = 0;
            gets(str);
            for(int j = 0; j < le; j += 3){
                a[i][m++] = (str[j] - '0') * 10 + (str[j+1] - '0');
            }
        }
        memset(dp, 0, sizeof(dp));
        memset(sum, 0, sizeof(sum));
        int cnt = 0;
        for(int i = 0; i < (1<<n); i++){
            if((i<<1)&i) continue;
            s[cnt++] = i;
        }
        //deal sum
        for(int i = 0; i < n; i++){
            for(int j = 0; j < cnt; j++){
                for(int k = 0; k < n; k++){
                    if(b[k]&s[j]){
                        sum[i][j] += a[i][k];
                    }
                }
            }
        }
        //INIT
        for(int i = 0; i < cnt; i++) dp[0][i] = sum[0][i];
        //DP
        for(int i = 1; i < n; i++){
            for(int j = 0; j < cnt; j++){
                for(int k = 0; k < cnt; k++){
                    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]);
                }
            }
        }
        int ans = 0;
        for(int i = 0; i < cnt; i++){
            ans = max(ans, dp[n-1][i]);
        }
        printf("%d\n",ans);
        getchar();
    }
    return 0;
}