【题解】E. Sending a Sequence Over the Network（1741）

链接：https://codeforces.com/problemset/problem/1741/E

题目大意

给出一个数组，判断它是否是合法的，如果合法则输出YES，不合法则输出NO。
合法规则：一段序列中，这个序列的第一个或者最后一个的数值，是这段序列的长度-1，那么我们就说这个序列是合法的。
例如：[8,3,2]就是一个合法的序列，因为2，是[8,3]的长度。
例如：1 1 2 3 1 3 2 2 3是一个合法的序列，因为[1,2,3,1,2,3] with the following partition: [1]+[2,3,1]+[2,3]. The sequence b: [1,1,2,3,1,3,2,2,3].（就原题的解释）

思路

这一眼看上去就知道，应该是动态规划的题目，为什么，这是因为，我们知道，一个区间是不是合法，它取决于，它前面的区间是否合法。
那么很简单啦，我们使用一个lastFind保存我们所有找到的合法区间，比如里面有个4就是到4这里是合法的，对于整个序列来说。好，那没了。就这样我们就可以写出下面的这样代码。

代码（TLE）

// VsCode C++模板 | (●'◡'●)
#include 
 
#include 
using namespace std;
typedef long long LL;
#define N 2 * 100000 + 5
int t, n, b[N];
bool check(int xi, int xy) {  //[xi,xy] 检查是否符合条件
    if (xi == xy) return false;
    if (b[xi] == (xy - xi) || b[xy] == (xy - xi)) {
        return true;
    } else {
        return false;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> b[i];
        }
        vector<int> lastFind{-1};//-1的话，是我们的默认开始值，这样第一个check就从0开始了，看下面的(-1)+1
        for (int i = 0; i < n; i++) {
            for (auto it = lastFind.begin(); it != lastFind.end(); it++) {
                if (check((*it) + 1, i)) {//如果前面合法，然后check也合法
                    lastFind.push_back(i);//那么到i这里肯定也合法
                    break;
                }
            }
        }
        bool ans = *(lastFind.end() - 1) == n - 1;//如果n-1是合法的，那就是Yes
        ans == true ? printf("YES\n") : printf("NO\n");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

所以小熊就洋洋洒洒地写出来了这些代码，很快啊，反手就Submit了。哎呦，不讲武德，居然是TLE了，这是为什么？仔细思考一下。

改进思路

原来是，这个程序最坏复杂度是$O(N^2)$，原来是这样，我们了解了。
问题出在

			for (auto it = lastFind.begin(); it != lastFind.end(); it++) {
                if (check((*it) + 1, i)) {//如果前面合法，然后check也合法
                    lastFind.push_back(i);//那么到i这里肯定也合法
                    break;
                }
            }
1
2
3
4
5
6

这个for循环里面，因为每一次都要去重新寻找，所以我们可以优化一下，这样就不用去寻找了。
如果我们已经得到了check(0,i)是合法的，那么check(i+1,i+1+b[i+1])如果不为空的话，那么在i+1+b[i+1]这个位置上，肯定也是能找到的，这些相当于利用了b[i+1]因为i已经合法了嘛，那一个描述字符串长度的数字，要么在左边，要么在右边，这相当于用了check(i+1,i+1+b[i+1])的左边数字，就是这么回事。
当然如果利用右边的数字，那更好判断了。

所以我们对每一个数字思考，到底用左边数字还是右边数字：
（1）取右边数字：

那么因为2可以作为指示长度的数字，所以我们猜测，到蓝色的那个位置，我们到底能不能配凑出一个真正符合题目的串。如果符合，那太好了。

 dp[i]=dp[i - b[i] - 1];
1

（2）取左边边数字：

这要求，必须当前i一定是true的，那么就可以得知，红色8这个位置，因为2的描述，所以也应该是可以为True的。注意一步真没后效性，因为我们是根据前面的True和
False的出的。
好，那就直接看代码吧，不复杂。

代码（AC）

// VsCode C++模板 | (●'◡'●)
#include 

#include 
using namespace std;
typedef long long LL;
#define N 2 * 100000 + 5
int t, n, b[N];
bool dp[N + 5];
int main() {
    ios::sync_with_stdio(false);
    cin >> t;
    while (t--) {
        cin >> n;
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; i++) {
            cin >> b[i];
        }
        for (int i = 0; i < n; i++) {
            //作为右边的数字
            if (i != 0 && i - b[i] >= 0) {
                if (i - b[i] == 0 || dp[i - b[i] - 1] == true) {
                    dp[i] = true;
                }
            }
            //作为左边的数字
            if (i == 0 && i + b[i] < n) {
                dp[i + b[i]] = true;
                continue;
            }
            if (i != 0 && i + b[i] < n && dp[i - 1] == true) {
                dp[i + b[i]] = true;
            }
        }
        dp[n - 1] == true ? printf("YES\n") : printf("NO\n");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

结语

题解写得详细，只望君能看懂。