方格取数(1)（状压dp）

Problem Description
给你一个nn的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。
Input
包括多个测试实例，每个测试实例包括一个整数n 和nn个非负数(n<=20)
Output
对于每个测试实例，输出可能取得的最大的和
Sample Input
3
75 15 21
75 15 28
34 70 5
Sample Output
188

状压dp
最后一行的状态取决于前面一行的状态，而前面一行的状态又取决于前面的。依次类推
通过枚举的方法，用二进制把每一种状态表示出来，例如，取一行中的第一和第三个，可以用 101 来表示
即十进制 5 。可以把所有合法的状态枚举出来，不合法的例如1011，连续两个1，不符合题意。
合法状态就是 i&(i<<1)，即i和i左移一位与一下，如果为0，证明i合法。例 01011 & 10110 = 00010不合法
然后遍历每一行，再枚举这一行的所有状态，把这一行状态取对应的值相加得到这一行的和，
把上一行的状态对比一下，看哪些符合题意，即 state[k] & state[j] = 0。
然后当前行保持的最大和上一行的最大和加这一行的值进行比较，更新这一行的最大值。
最后一行 dp[n][i] 即为第n行，i状态下对应得最大值

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

int n,mapp[20][20];
int dp[20][1<<17],state[1<<17];


int main()
{
    int m;
    while(~scanf("%d",&n))
    {
        for(int i = 1; i<=n; i++)
        {
            for(int j = 1; j<=n; j++)
            {
                scanf("%d",&mapp[i][j]);
            }
        }
        memset(dp,0,sizeof(dp));
        int cnt = 0;
        for(int i = 0; i<(1<<17); i++)//枚举一行中可能出现的合法状态。
        {
            if(!(i&(i<<1)))
                state[cnt++] = i;
        }

        for(int i = 1; i<=n; i++)//遍历每一行
        {
            for(int j = 0; j<cnt; j++)//枚举第i行可能出现的情况
            {
                int s = 0;
                for(int k = 0; k<n; k++)//把第i行这种状态下对应的值相加
                {
                    if(state[j]&(1<<k))
                        s+=mapp[i][k+1];
                }
                for(int k = 0; k<cnt; k++)//看第i-1行有哪些情况满足第i行的状态
                {
                    if(!(state[k]&state[j]))
                        dp[i][j] = max(dp[i][j],dp[i-1][k]+s);//比较取大的
                }
            }
        }
        int ans = 0;
        for(int i = 0; i<cnt; i++)
        {
            ans = max(ans,dp[n][i]);//最后一行每种状态的最大值
        }
        printf("%d\n",ans);
    }
    return 0;
}