【题解】CF1741E

· · 题解

更好的阅读体验

本蒟蒻的第一篇题解。

这道题我看大家都是用一维 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;
    }
}