CF1616D Keep the Average High

题目描述

给定一个长 $n$ 的数列 $a$ ，再给定一个 $x$ 。你需要选中其中一些数，使得对于所有连续的被选中的长度至少为 $2$ 的子串 $[l,r]$ 满足：

\sum_{i=l}^ra_i\ge (r-l+1)\times x

求最多能选出多少个数。

思路

主要讲一下思考过程。首先肯定是将 $a_i$ 全部减掉 $x$ 。

接下来往下思考，所有的选中的长度大于等于 $2$ 的子串，这个条件很棘手，考虑找一个等价的简化命题。不难发现，可以转化为所有长度等于 $2$ 和 $3$ 的子串和大于 $0$ ，显然地，所有的长度大于等于 $2$ 的子串都可以分割为若干个长度为 $2$ 或 $3$ 的子串拼接起来。

然后我们发现，对于一个数字的决策，只跟前两个数字的决策有关，那么可以考虑动态规划。

设 $f_{i},g_{i},h_i$ 分别表示 $a_i$ 不取， $a_i$ 取但是 $a_{i-1}$ 不取， $a_i$ 取 $a_{i-1}$ 也取时的最大价值。

考虑转移。

对于 $f_i$ 和 $g_i$ ，转移都是很显然的：

f_i = \max\{f_{i-1},g_{i-1},h_{i-1}\}

g_i=f_{i-1} + 1

接下来看 $h_i$ 的转移：

加入第 $i$ 个是最后一段连续段的第 $3$ 个或更多时，当 $a_{i-2}+a_{i-1}+a_{i} \ge 0$ 且 $a_{i-1} + a_i \ge 0$ 时才可以选，此时转移为：

h_i=h_{i-1}+1

加入第 $i$ 个是最后一段连续段的第 $2$ 个时，当 $a_{i-1} + a_i \ge 0$ 时才可以选，此时转移为：

h_i=g_{i-1}+1

然后这道题就做完了，时间复杂度为 $\Theta(n)$ 。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 10;

int T, A[MAXN], X,  N;
int Dp[3][2];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while (T--) {
        cin >> N;
        A[0] = -1114514;
        for (int i = 1; i <= N; i++) {
            cin >> A[i];
        }
        cin >> X;
        for (int i = 1; i <= N; i++) {
            A[i] -= X;
        }
        memset(Dp, 0, sizeof Dp);
        for (int i = 1; i <= N; i++) {
            Dp[0][i & 1] = max({Dp[0][(i - 1) & 1], Dp[1][(i - 1) & 1], Dp[2][(i - 1) & 1]});
            Dp[1][i & 1] = Dp[0][(i - 1) & 1] + 1;
            if (A[i] + A[i - 1] >= 0) {
                Dp[2][i & 1] = Dp[1][(i - 1) & 1] + 1;
                if (i >= 2 && A[i - 2] + A[i - 1] + A[i] >= 0) {
                    Dp[2][i & 1] = max(Dp[2][i & 1], Dp[2][(i - 1) & 1] + 1);
                }
            }
        }
        cout << max({Dp[0][N & 1], Dp[1][N & 1], Dp[2][N & 1]}) << endl;
    }
    return 0;
}