BZOI 2017-07-11集训 T2(状压DP)

类似于poj1185,但是这里的影响范围是它曼哈顿距离为$2$的格子,也就是说处理状态变得复杂了很多。
设$dp(i, st(j), st(k))$为第$i$行用状态$k$,第$i-1$行用状态$j$的最优值。那么转移方程即为:
$$dp(i, st(j), st(k)) = max(dp(i, st(t), st(j)) + num(k))$$
怎么处理状态?先处理每行可行方案,1、不能有三个连续的摆放 2、不能有两个摆放之间距离为$2$
按位DP的时候,$i$上面一行对$i$行的影响只有两个方格,具体是哪个画图就知道。$i$上面第二行对$i$行的影响只有一个方格,同样具体是哪个画图就知道。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 "soldier"
using namespace std;
const int MAXN = 100 + 5;
int n, m, num[200 + 5], cur[MAXN], st[200 + 5], dp[MAXN][200 + 5][200 + 5], top;
int js(int x) {
int ret = 0;
while (x) {
ret++;
x&=(x-1);
}
return ret;
}
int check(int x) {
int tot = 0, tot2 = 0;
while (x) {
if (x&1) {
if (tot2==1&&tot!=-1) return false; else if (tot2>=1) tot = 0;
tot2 = 0, tot++;
if (tot>=3) return false;
} else {
tot2++;
if (tot==0) tot = -1;
}
x>>=1;
}
if (tot>=3) return false;
return true;
}
int check2(int up, int down) {
int i = 0;
while (up) {
if (up&1) {
if (i-1>=0&&(down>>(i-1))&1) return false;
if (i+1<m&&(down>>(i+1))&1) return false;
}
up>>=1, i++;
}
return true;
}
bool fit(int s1, int h) {return (s1&cur[h]) ? false : true;}
void clean() {
top = 1, ms(dp, -1), st[top] = 0;
}
void solve() {
clean();
for (int i=1;i<(1<<m);i++) if (check(i)) st[++top] = i, num[top] = js(i);
for (int i=1;i<=n;i++) {
cur[i] = 0;
for (int j=1;j<=m;j++) {
int x; scanf("%d", &x);
if (!x) cur[i] += (1<<(j-1));
}
}
for (int i=1;i<=top;i++) {
if (fit(st[i], 1)) dp[1][i][1] = num[i];
}
for (int hi=2;hi<=n;hi++) {
for (int i=1;i<=top;i++) {
if (fit(st[i], hi)) {
for (int j=1;j<=top;j++) {
if (check2(st[j], st[i])&&fit(st[j], hi-1)) {
for (int k=1;k<=top;k++) {
if (st[k]&st[i]) continue;
if (dp[hi-1][j][k]==-1) continue;
if (check2(st[k], st[j])&&fit(st[k], hi-2)) dp[hi][i][j] = max(dp[hi][i][j], dp[hi-1][j][k] + num[i]);
}
}
}
}
}
}
int ans = 0;
for (int hi=1;hi<=n;hi++) {
for (int i=1;i<=top;i++) {
for (int j=1;j<=top;j++) {
ans = max(ans, dp[hi][i][j]);
}
}
}
printf("%d\n", ans);
}
int main() {
freopen(FN2".in", "r", stdin); freopen(FN2".out", "w", stdout);
while (scanf("%d%d", &n, &m)==2&&n&&m) solve();
fclose(stdin); fclose(stdout);
return 0;
}

Soldier
1s
Problem Description
  郑厂长不是正厂长
  也不是副厂长
  他根本就不是厂长
  事实上
  他是带兵打仗的团长

  一天,郑厂长带着他的军队来到了一个n*m的平原准备布阵。
  根据以往的战斗经验,每个士兵可以攻击到并且只能攻击到与之曼哈顿距离为2的位置以及士兵本身所在的位置。当然,一个士兵不能站在另外一个士兵所能攻击到的位置,同时因为地形的原因平原上也不是每一个位置都可以安排士兵。
  现在,已知n,m 以及平原阵地的具体地形,请你帮助郑厂长计算该阵地,最多能安排多少个士兵。

Input
输入包含多组测试数据;
每组数据的第一行包含2个整数n和m (n <= 100, m <= 10 ),之间用空格隔开;
接下来的n行,每行m个数,表示n*m的矩形阵地,其中1表示该位置可以安排士兵,0表示该地形不允许安排士兵。

Output
请为每组数据计算并输出最多能安排的士兵数量,每组数据输出一行。

Sample Input
6 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Sample Output
2

------ 本文结束 ------