HDU1565 方格取数(1)(状态压缩dp)

题目链接。

分析：

说这题是状态压缩dp，其实不是，怎么说呢，题目数据太水了，所以就过了。手动输入n=20的情况，超时。正解是网络流，不太会。

A这题时有个细节错了，是dp[i][j]还是dp[i][q[j]]? 答案是dp[i][j],因为q[j]必定会超（感谢CZ学长提示）。

AC代码如下：

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

const int maxn = 20000;

int q[maxn], dp[21][maxn], G[21][21];

int main() {
    int n;

    while(scanf("%d", &n) == 1) {
        int cn = 0;
        for(int i=0; i<(1<<n); i++) {
            if((i & (i << 1)) == 0) {
                q[cn++] = i;
            }
        }

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

        memset(dp, 0, sizeof(dp));

        for(int i=1; i<=n; i++) {
            for(int j=0; j<cn; j++) {
                int ans = 0;
                for(int p=0; p<n; p++) {
                    if((q[j]&(1<<p)) != 0) {
                        ans += G[i][p+1];
                    }
                }

                dp[i][j] = ans;

                for(int k=0; k<cn; k++) {
                    if((q[j] & q[k]) == 0) {
                        dp[i][j] = max(dp[i][j], dp[i-1][k]+ans);
                    }
                }
            }
        }

        int ans = -1;
        for(int i=0; i<cn; i++) {
            ans = max(ans, dp[n][i]);
        }

        printf("%d
", ans);
    }

    return 0;
}