题解 P2327 【[SCOI2005]扫雷】
小黑AWM
2019-03-30 18:00:20
看完了所有题解,没看到有记忆化搜索的,遂交一发。
### 思路
一开始做题的时候第一秒莫名就想到枚举,不过好在脑子还正常,以at表示当前搜到第几个点,stat是一个3位二进制数表示在该点拓展之前,这个点的左边三联通的地雷状况,1表示有雷,0表示无雷。后考虑每个点在拓展时其实只能在最后一个点选择是否有雷才能防止影响之前的决策,那么只要计算出这个点还能放多少雷就可以判断了。
配合图表来解释一下:
| 雷 |数 |
| :----------: | :----------: |
| 1 | 2 |
| 1 | 1 |
| 0 | 2 |
| * | 1 |
当我们搜索到倒数第二行时,只能在*处选择是否置雷才可以防止之前的递推结果被破坏,又由于在无法改变的过去中2的左边和上边已经放了一个雷,所以还要放一个雷然后继续递推下去即可,用一个f数组记录答案即可。这个状态设计可以保证是没有后效性的。
### 边界情况
1. 由于第0个数无法搜索,我们需要对于 $(1,(000)B)$ 和 $(1, (010)B)$ 两种状态分别进行搜索,最后把答案 $f[1][0]$ 和 $f[1][2]$ 加起来即可。
2. 对于最后一个数,因为它不能修改他之后的情况,所以在搜索时对于最后一个数要求我们当前已满足其所要求的条件。
```cpp
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 1e4 + 10;
int n, a[maxn], f[maxn][8];
bool visit[maxn][8];
int dfs(int at, int stat){
if(visit[at][stat])
return f[at][stat];
visit[at][stat] = true;
int val = a[at];
for(int i = 0; i <= 2; i++)
val -= (stat >> i) &1;
if(val > 1 || val < 0)
return f[at][stat] = 0;
if(at == n && val == 0)
return f[at][stat] = 1;
if(val == 0)
f[at][stat] += dfs(at+1, (stat << 1)&7);
if(val == 1)
f[at][stat] += dfs(at+1, ((stat|1) << 1)&7);
return f[at][stat];
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
cout << dfs(1, 0) + dfs(1, 2) << endl;
return 0;
}
```
不过虽说形式是记忆化搜索,但是究其本质,还是一种写法略有不同的递推……