[CF2025D]Attribute Checks 解题思路

题目大意（翻译来自luogu）

给定两个正整数 \(n\) 和 \(m\)，以及一个长度为 \(n\) 的数组 \(r\)。保证 \(-m \le r_i \le m\)，并且恰好有 \(m\) 个 \(r_i\) 为 \(0\)。

你有两个初始值均为 \(0\) 的变量 \(I\) 和 \(S\)，接下来在第 \(i\) 秒中（\(1 \le i \le n\)）将发生如下事件：

• 如果 \(r_i > 0\) 并且此时 \(I \ge |r_i|\) ，则你获得一分。

• 如果 \(r_i < 0\) 并且此时 \(S \ge |r_i|\)，则你获得一分。

• 如果 \(r_i = 0\)，则你需要从以下两种决策中选择一种：将 \(I\) 的值增加 \(1\)，或者将 \(S\) 的值增加 \(1\)。

求你最终能获得分数的最大值。

数据范围

\(0\leq m \leq 5000\)
\(m < n \leq 2\cdot 10^6\)

时空限制

• 2.5 seconds
• 512 megabytes

思路

注意到这里 \(m\) 的范围和时间限制，明显可以考虑 \(O(m^2)\) 时间复杂度的算法。
我们发现，只有当 \(r_i = 0\) 的时候才能使 \(S,I\) 的值改变，换言之，每次在 \(r_i\) 处进行决策。
考虑dp，我们可以建立数组 \(dp[i][j]\) 表示 \(I=i ,S=j\) 时候的获得分数的最大值，显然，这时候是第 \(i+j\) 次决策。
每一次决策我们可以从 \(dp[i-1][j]\) 和 \(dp[i][j-1]\) 转移而来。
我们将 \(0\) 定义为“决策数”
每一次决策过后，会增加一些分数，如果 \(I\) 增加为 \(I+1\)，那么增加的分数将会是在这个“决策数”之后的 \(r_i=I+1\) 的数量，因为当上一次对 \(I\) 进行增加时，已经将 \(r_i=I\) 所获的分数加过了。
对于获得每一次决策后，这个“决策数”后面每一个数字的数量 \(m^2\) 打桶即可。

	#include<bits/stdc++.h>
using namespace std;
#define ll long long
int pot1[5010][5010],pot0[5010][5010];int n,m,cnt;
//pot1[i][j]代表第m-i次决策的r后面大于0的数字j 的个数
//pot1[i][j]代表第m-i次决策的r后面小于0的数字，绝对值j 的个数
ll dp[5010][5010];
int main(){
    //freopen("read.in","r",stdin);
    stack<ll>st;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        ll l;
        scanf("%lld",&l);
        st.push(l);
    }
    while(!st.empty()){
        int l=st.top();
        st.pop();

        if(l==0){
            cnt++;
            for(int i=0;i<=m;++i)pot1[cnt][i]=pot1[cnt-1][i],pot0[cnt][i]=pot0[cnt-1][i];
        }
        if(l<0)pot0[cnt][-l]++;
        if(l>0)pot1[cnt][l]++;
    }
    for(int i=1;i<=m;++i){
        for(int j=0;j<=m;++j){
            if(j-1>=0)dp[j][i-j]=max(dp[j][i-j],dp[j-1][i-j]+pot0[m-i][j]);
            if(i-j-1>=0)dp[j][i-j]=max(dp[j][i-j],dp[j][i-j-1]+pot1[m-i][i-j]);
        }
    }
    ll mxn=0;
    for(int i=0;i<=m;++i)mxn=max(mxn,dp[i][m-i]);
    printf("%lld",mxn);
}