方格取数

给你一个n∗n的格子的棋盘，每个格子里面有一个非负整数。
你需要从中取出若干个数，使得任意两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。

输入描述:

每个测试实例包括一个整数n 和n∗n个非负整数，保证每个数不超过。

示例1
输入

3
75 15 21
75 15 28
34 70 5

输出

188

说明

n<=16，每个数不超过 10^3。

fanggequshu.cppview raw

#include <iostream>
using namespace std;

int n;
const int N = 20;
int mp[N][N], dp[N][70000];
int A[30005], tot;

int calc(int x, int y){
    int res =0;
    int j = n;
    while(y){
        if(y&1) res += mp[x][j];
        j--; y>>=1;
    }
    return res;
}

int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d", &mp[i][j]);


    for(int i=0;i<(1<<n);i++){
        if((i&(i>>1))==0) A[++tot] = i;
    }


//    dp[i][k] = max(dp[i][k], dp[i-1][j] + val(i-1, j))
    for(int i=1;i<=n;i++)
        for(int k=1;k<=tot;k++){
            for(int j=1;j<=tot;j++){
                if((A[j] & A[k]) ==0){
                    int val = calc(i, A[k]);
                    dp[i][k] = max(dp[i][k], dp[i-1][j] + val);
                }
            }
        }

    int ans = 0;
    for(int i=1;i<=tot;i++) ans = max(ans, dp[n][i]);
    printf("%d\n", ans);
    return 0;
}