识海社区打卡-2

今天打卡一道题，白天太忙了，没时间打卡树状数组，昨天就睡了三小时就去软考了差点没猝死我，回来路上还见识到了哈尔滨公交车的险恶导致下午三点才到校，花了一个小时吃饭洗漱然后就睡觉了，7点起到工位上，看了会昨天cf的题解摆烂了一会就到十点了，得抓紧更新打卡然后接着cf，明天还有早八悲，感觉已经在猝死的边缘反复横跳了。

题目链接：Problem - C - Codeforces

这题昨晚花了我两小时也没解出来，第一眼就是dp类型，但我确实当时没想到怎么dp就想了别的方法。

首先理解下题目的意思，就是给定一个数组a，然后一个返回值ans = 0，当数组a中的数a[i] > ans,ans++,else ans--；然后可以选择一个区间进行跳过，使得最后的返回值最大。

我当时的想法是这有两种情况，一种是前缀最大就是最大，到了某个位置后ans大于了后面的所有数字，那么返回这个最大值就好了，还有一种情况就是跳过中间的某一段然后答案就是前面的最大再加上最后的一段。

想法有了如何实现，我是先建立一个找到最大的前缀x，然后记录最大前缀的位置，往后的数全减去最大前缀x，然后重复之前找最大前缀的操作就行了。但这个方法在测试样例的时候出了一点问题。

且看样例1,2,1,1,1,3,4

这个样例如果自己算的话就是跳过中间三个1，但是按照上面的实现方法就变成了最大前缀在最后的位置，x = 3，显然不符合答案，所以我新增加了一种机制，就是如果最大前缀的位置并且最大前缀不等于n的时候再往中间找最大的递减区间。很好这回过样例了，但提交后就wa2了

好吧其实到比赛最后我也不知道问题出在哪，在比赛结束后只看到一行

wrong answer 59th numbers differ - expected: '2', found: '3'

经过我的一番操作居然让答案变大了？？？好吧我确实不知道问题出在哪了，毕竟经过了两个小时的修改代码早已经和屎没有任何区别，这样的代码估计改了多少次依旧是狗屎一坨，还是得用dp了解决。

constexpr int inf = 1E9;

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    std::array<int, 3> dp {0, -inf, -inf};
    for (int i = 0; i < n; i++) {
        dp[2] = std::max(dp[2], dp[1]);
        dp[1] = std::max(dp[1], dp[0]);
        for (int j = 0; j < 3; j++) {
            if (j == 1) {
                continue;
            }
            int &x = dp[j];
            if (a[i] > x) {
                x++;
            } else if (a[i] < x) {
                x--;
            }
        }
    }
    
    std::cout << std::max(dp[1], dp[2]) << "\n";
}

要想提高自己的代码的水平还是得多看看哥哥的代码，哥哥的动态规划，dp[0]就相当于我的找前缀，dp[1]相当于我的找最大前缀，dp[2]则是找后缀，嗯好像想法和我的差不多，只是我写的太屎了，多多像哥哥学习。