Div. 3 Codeforces Round #826 A-E( 二 ) _生活百科

E知识点：线性dp 。
朴素dp，设 \(dp[i]\) 为 \([1,i]\) 是否合法。考虑 \(b[i]\) 时，可以把其放下一段左侧或者是右侧，因此有转移方程：
if (i - b[i] - 1 >= 0) dp[i] |= dp[i - b[i] - 1];if (i + b[i] <= n) dp[i + b[i]] |= dp[i - 1];时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
题解代码#include <bits/stdc++.h>#define ll long longusing namespace std;int b[200007];bool dp[200007];bool solve() {int n;cin >> n;for (int i = 1;i <= n;i++) cin >> b[i], dp[i] = 0;dp[0] = 1;for (int i = 1;i <= n;i++) {if (i - b[i] - 1 >= 0) dp[i] |= dp[i - b[i] - 1];if (i + b[i] <= n) dp[i + b[i]] |= dp[i - 1];}if (dp[n]) cout << "YES" << '\n';else cout << "NO" << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}