[HDU1565] 方格取数(1)
2017年9月19日给你一个n * n的格子的棋盘,每个格子里面有一个非负数。从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取的数所在的2个格子不能相邻,并且取出的数的和最大。
状态压缩DP,设dp[i][j]
为第 i 行状态为 j 的最大和,则dp[i][j] = \\max(dp[i – 1][k]) + sum_j,其中,sum_j表示状态为 j 时所能得到的和,j表示第i行的状态,k表示第i – 1行的状态,且要满足 k 与 j 中的数不相邻。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 30000;
int state[N], a[25][25];
int dp[25][N];
int main()
{
int n;
while (~scanf("%d", &n)) {
int cnt = 0;
for (int i = 0; i < 1 << n; i++) {
if (i & i << 1)
continue;
state[cnt++] = i;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &a[i][j]);
}
}
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) {
for (int j = 0; j < cnt; j++) {
for (int k = 0; k < n; k++) {
//把状态 j 的和求出来
if (state[j] & 1 << k) {
dp[i][j] += a[i][k];
}
}
int tmp = 0;
//找出第 i - 1 行中最大的和
for (int k = 0; k < cnt; k++) {
//如果状态 j 与状态 k 有相邻的,则跳过
if (state[j] & state[k]) {
continue;
}
tmp = max(tmp, dp[i - 1][k]);
}
dp[i][j] += tmp;
}
}
int ans = 0;
for (int i = 0; i < cnt; i++) {
ans = max(ans, dp[n][i]);
}
printf("%d\n", ans);
}
return 0;
}