問題#
[NOI2001] 砲兵陣地#
司令部の将軍たちは $N\times M$ のグリッドマップ上に彼らの砲兵部隊を配置することを計画しています。
$N\times M$ のマップは $N$ 行 $M$ 列で構成され、マップの各セルは山地（$\texttt {H}$ で表示）または平原（$\texttt {P}$ で表示）である可能性があります。以下の図のように。
各平原地形のセルには最大で 1 つの砲兵部隊を配置できます（山地には砲兵部隊を配置できません）；砲兵部隊のマップ上での攻撃範囲は図中の黒い領域で示されています：
マップ中の灰色で示された平原に砲兵部隊を配置すると、図中の黒いセルはその部隊が攻撃できる範囲を示しています：横方向に左右各 2 セル、縦方向に上下各 2 セル。
図の他の白いセルは攻撃できません。図からもわかるように、砲兵の攻撃範囲は地形の影響を受けません。
現在、将軍たちは砲兵部隊をどのように配置するかを計画しており、誤射を防ぐ前提の下（任意の 2 つの砲兵部隊が互いに攻撃できないように、つまり任意の砲兵部隊が他の砲兵部隊の攻撃範囲内にないように）、マップ全体の領域内に最大で何個の我が軍の砲兵部隊を配置できるかを考えています。
$100%$ のデータに対して、$N\le 100$、$M\le 10$、文字は P と H のみで構成されることが保証されています。
解答#
まずデータ範囲を見て、直接状態圧縮 dp を考えます。
状態を設計することを考えます。
まず f[i][j] を第 i 行に到達し、かつ第 i 行の状態の二進数が j であるとき、配置できる最大の砲兵部隊数を表すことを試みます。
遷移を試みます。
f [i][j] は f [i-1][~] から遷移する必要がありますが、f [i-1][~] の状態に含まれる集合はすべて使用できるわけではないため、遷移できません。
状態を追加することを考えます。
f[i][j][fl] は第 i 行に到達し、かつ第 i 行の状態の二進数が j であり、第 i-1 行の状態が fl であるとき、配置できる最大の砲兵部隊数を表します。
これで遷移できるようになりました。
実装#
配置できるかどうかを判断し、二進数とマップを比較し、二進数自体をそれぞれ左に 1 ビット、2 ビットシフトして比較します。
他は同様です。
問題が発生しました#
-
状態圧縮 dp はインデックスを 0 から始めるのが最適です。
-
ローリング配列を学びました。
コード#
#include<bits/stdc++.h>
using namespace std;
int read()
{
int f = 1, x = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return f * x;
}
int n, m;
int Map[110];//1なら山地、0なら平原
int f[3][1 << 10][1 << 10]; // i、現在の状態、前の行の状態
int num_of_1[1 << 10];
int getsum(int x)
{
int ans = 0;
while(x)
{
x &= (x - 1);
ans++;
}
return ans;
}
int main()
{
for(int i = 0;i < (1 << 10);i++)
{
num_of_1[i] = getsum(i);
}
n = read(), m = read();
char ch;
for(int i = 0;i < n;i++)
{
for(int j = 0;j < m;j++)
{
cin >> ch;
if(ch == 'H')
{
Map[i] |= (1 << j);
}
}
}
for(int j = 0;j < (1 << m);j++)
{
if(j & (j << 1) || j & (j << 2) || j & Map[0]) continue;
f[0][j][0] = num_of_1[j];
}
for(int j = 0;j < (1 << m);j++)
{
for(int fl = 0;fl < (1 << m);fl++)
{
if(j & (j << 1) || j & (j << 2) || j & Map[1] || fl & (fl << 1) || fl & (fl << 2) || fl & Map[0] || j & fl || j & Map[1])
continue;
f[1][j][fl] = num_of_1[j] + num_of_1[fl];
}
}
for(int i = 2;i < n;i++)
{
for(int j = 0;j <= (1 << m) - 1;j++)//現在の行
{
if(j & Map[i] || j & (j << 1) || j & (j << 2))
{
continue;
}
for(int fl = 0; fl <= (1 << m) - 1;fl++)//前の行
{
if(fl & Map[i - 1] || fl & (fl << 1) || fl & (fl << 2) || j & fl)
{
continue;
}
for(int fll = 0; fll < (1 << m);fll++)
{
if(fll & Map[i - 2] || fll & (fll << 1) || fll & (fll << 2) || j & fll || fl & fll)
{
continue;
}
f[i % 3][j][fl] = max(f[i % 3][j][fl], f[(i - 1) % 3][fl][fll] + num_of_1[j]);
}
}
}
}
int ans = 0;
for(int j = 0;j < (1 << m);j++)
{
for(int fl = 0;fl < (1 << m);fl++)
{
ans = max(ans, f[(n - 1) % 3][j][fl]);
}
}
cout << ans << endl;
return 0;
}