狡兔三窟问题（猎人抓兔子）

狡兔三窟

n 个连续的洞（编号1-n），兔子白天待在洞里，晚上跳到相邻的洞里。猎人白天检查，希望找到兔子。给定洞口数 n，检查天数 k 以及 k 个检查洞口编号，输出是否能抓住兔子。

e.g.

输入

3 2

2 2

输出

Yes

初印象

对于第 i 个洞口，当 i = 1 或 i = n 时，只有一种选择，其它情况下可以 +1 也可以 -1.

对于兔子的状态，可以想象到一个有向图，或者一个状态机。

正确思想

这题的关键就在于状态。这里并没有设计很复杂的状态设计，反而很直觉：设置一个长度为 n 的 01 数组，表示兔子是否有可能出现在该位置上。

思路1

首先将所有洞口的值置为1，表示兔子可能在此洞中；假设猎人每次检查洞口都抓不到兔子(兔子不在此洞中)，将该洞口的值置为0；再将每天晚上兔子可能跳到的洞口值置为1，不可能跳到的洞口值置为0，当所有的洞口全为0的时候兔子无洞可逃，则肯定会被猎人抓住。

思路2

可以呆的洞为1，不可以的为0，先全部初始化为1，横坐标代表洞的标号，纵坐标代表第几天。第j天被检查的洞一定是0；如果是1号洞或是m号洞，则查看前一天的二号洞或m-1号洞是0的话，1号洞或m号洞为0；如果前一天的i-1和i+1号洞都是0的话，第i号洞为0。 填表完成之后，遍历数组的最后一行，如果有1的话，代表兔子有可能不被抓住，如果全为0，则代表一定会被抓住。

从状态转移的角度讲，一定是第 i 个洞口为 1，i+1 和 i-1才能设置为 1。所以初始状态应该是全 1，然后下一个状态初始化为全 0，依次设置为 1，然后再将猎人看中的洞口设置为0. 循环往复，最终全 0 就说明一定能捉到。

代码

# include

# include

const int N = 3005;

using namespace std;

int main(void) {

int n, k;

cin >> n >> k;

vector dp(n, 1), a(k+1);

for (int i = 1; i <= k; i ++ ) cin >> a[i];

for (int i = 1; i <= k; i ++ ) {

vector nextdp(n+2, 0);

for (int j = 1; j <= n; j ++ )

if (dp[j]) nextdp[j-1]=nextdp[j+1]=1;

nextdp[a[i]] = 0;

swap(nextdp, dp);

for(int j = 1; j <= n; j ++ ) cout << dp[j] << ' ';

cout << '\n';

}

return 0;

}