题解：Sending a Sequence Over the Network

更好的阅读体验

本蒟蒻的第一篇题解。

这道题我看大家都是用一维 DP 做的，本蒟蒻今天在考场上写了种二维 DP 的做法。我个人认为这种可能理解起来会简单一些（虽说写起来麻烦了点），于是就有了这篇题解。

思路

当时（考场上）想了半天没想出来怎么使用一维 DP 解决这道题，便想了一种二维 DP 的做法。

我们定义 $f[0][i]$ 表示以 $i$ 作为一段的头部时是否可行，$f[1][i]$ 表示以 $i$ 作为一段的结尾是否可行。并且在原序列中添加两个点：$0$ 和 $n+1$。

状态转移（以下 $i$ 均指当前考虑的位置）：

• 头的转移

1. 如果上一个位置可以作为尾，那么这个位置就可以作为头。
   也就是 $f[0][i] = f[1][i-1]$
2. 如果当前位置作为头，那么下一段的头的位置也可以作为头。
   也就是 $f[0][i+a[i]+1] = f[0][i]$

• 尾的转移

1. 如果上一段的尾的位置可以做尾，则当前位置可以做尾。
   也就是 $f[1][i] = f[1][i-a[i]-1]$
2. 如果这一段的头的位置可以做头，那么当前位置也可以做尾。
   也就是 $f[1][i]=f[0][i-a[i]]$

注意：写代码的时候要注意下标不能越界。

根据以上的转移（可能有点乱），我们能知道初始状态为：
$$
f[1][0] = f[0][1] = 1
$$

而最后我们只需要判断第 $n$ 个位置能否做尾或第 $n+1$ 个位置能否做头就好。

代码

（供群众批判）

#include <bits/stdc++.h>
using namespace std;

int n;
int a[200010];
bool f[2][200010];
/*
  0: 作为头
  1: 作为尾
 */

int main() {
	int T;
	cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];
		memset(f, 0, sizeof f); // 多测不清空，爆零两行泪
		f[1][0] = 1;
		f[0][1] = 1;
		for (int i = 1; i <= n; i++) {
			// i作为头
			// 从上一个是尾转移
			f[0][i] |= f[1][i-1];
			// 隐藏情况：之前有人帮它更新了
			// 更新下一个可能作为头的
			if (f[0][i] && i+a[i]+1 <= n+1) f[0][i+a[i]+1] = 1;
			// i作为尾
			if (i-a[i]-1 >= 0) f[1][i] |= f[1][i-a[i]-1];
			if (i-a[i] >= 0) f[1][i] |= f[0][i-a[i]];
		}
		if (f[1][n] || f[0][n+1]) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
}