状态压缩DP

I - 方格取数(1)

Submit Status

Description

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

Input

包括多个测试实例，每个测试实例包括一个整数n 和n*n个非负数(n<=20)

Output

对于每个测试实例，输出可能取得的最大的和

Sample Input

Sample Output

思路：

先算出一行的每个dp,然后枚举以后的每一行，他的dp就是他加上上一行中不冲突的最大的那个dp.第二道状态压缩DP，还是参照了别人的博客，写了这两个状压DP，已经对状压DP理解了很多了。（下面说的C题是上一篇博客的题）

代码：

#include <iostream>
#include <cstdio>
#include <cstdio>
#include <cstring>
using namespace std;
using ll = long long;
int n, a[21][21], sn[1 << 14], tot;
ll f[21][1 << 14], dp[21][1 << 14];
void init()
{
    tot = 0;
    for (int i = 0; i < (1 << n); ++i) {
        if (i & (i << 1)) continue;
        else sn[++tot] = i;
    }
    for (int i = 0; i < n; ++i) {
         for (int j = 1; j <= tot; ++j) {
             f[i][j] = 0;
             for (int h = 0; h < n; ++h) {
                 if ((sn[j] >> h) & 1) f[i][j] += a[i][h];
             }
         }
    }
}
int main()
{
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                scanf("%d", &a[i][j]);
            }
        }
        init();
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= tot; ++i) dp[0][i] = f[0][i];
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= tot; ++j) {
                for (int h = 1; h <= tot; ++h) {
                    if (sn[j] & sn[h]) continue;
                    dp[i][h] = max(dp[i][h], dp[i - 1][j] + f[i][h]);
                }
            }
        }
        ll ans = 0;
        for (int i = 1; i <= tot; ++i) {
            ans = max(ans, dp[n - 1][i]);
        }
        printf("%lld
", ans);
    }
    return 0;
}