题目描述

题目传送门

给定一个长 nn 的数列 aa,再给定一个 xx。你需要选中其中一些数,使得对于所有连续的被选中的长度至少为 22 的子串 [l,r][l,r] 满足:

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

求最多能选出多少个数。

思路

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

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

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

fi,gi,hif_{i},g_{i},h_i 分别表示 aia_i 不取,aia_i 取但是 ai1a_{i-1} 不取,aia_iai1a_{i-1} 也取时的最大价值。

考虑转移。

对于 fif_igig_i,转移都是很显然的:

fi=max{fi1,gi1,hi1}f_i = \max\{f_{i-1},g_{i-1},h_{i-1}\}

gi=fi1+1g_i=f_{i-1} + 1

接下来看 hih_i 的转移:

加入第 ii 个是最后一段连续段的第 33 个或更多时,当 ai2+ai1+ai0a_{i-2}+a_{i-1}+a_{i} \ge 0ai1+ai0a_{i-1} + a_i \ge 0 时才可以选,此时转移为:

hi=hi1+1h_i=h_{i-1}+1

加入第 ii 个是最后一段连续段的第 22 个时,当 ai1+ai0a_{i-1} + a_i \ge 0 时才可以选,此时转移为:

hi=gi1+1h_i=g_{i-1}+1

然后这道题就做完了,时间复杂度为 Θ(n)\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;
}