题解：CF2025D Attribute Checks

Misaka屮Mikoto · 2024-10-23 10:03:21 · 题解

CF2025D Attribute Checks

题目大意

给定两个正整数 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。

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

数据范围

时空限制

• 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);
}