题解：【NOIP2024模拟测试 #33】变幻

Nagato_ · 2024-11-24 21:13:57 · 题解

题目描述

如果数组 a 中有任意一个点 i 满足 a[i-1] > a[i] 且 a[i] < a[i+1] ，我们则称这个点 i 为“山谷点”。注意，数组中第一个元素和最后一个元素永远不可能为山谷点。

一个数组的价值是所有山谷点之和。至多修改 k 次数组，每次修改可以任选一个位置，使得这个位置上的数字变得比原来更小。你希望数组的价值最大，求最大价值。

输入格式

第一行包含两个正整数 n 和 k ，意义如题面所示。

接下来一行包含 n 个正整数，表示数组中的元素 a_i 。

输出格式

输出一行一个正整数，表示答案。

题解

看到这道题，我们明显发现，是一个DP，我们用 f_{i,j,0/1} 表示状态，i 表示考虑到前 i 个位置，j 表示已经变换过 j 次，0/1 表示这个位置有没有得分。

注意，不能用 0/1 表示有没有change，因为就算没有change，得分后也不能再改变下一个点。

那么，状态转移显然，详见代码，注意题目要求 <，记得 -1。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,k,a[2010],f[2010][2010][2],ans;  // 0 - not point , 1 - is point
int main()
{
    freopen("t1.in","r",stdin);
    freopen("t1.out","w",stdout);

    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);

    if(a[2]<a[1] && a[2]<a[3])
        f[2][0][1] = a[2];
    else
        f[2][1][1] = min(a[1],a[3])-1 ;

    for(int i=3;i<=n;i++)
    {
        for(int j=0;j<=k;j++)
        {
            if(a[i]<a[i-1] && a[i]<a[i+1])
                f[i][j][1] = f[i-1][j][0] + a[i] ;
            else if(j>=1)
                f[i][j][1] = f[i-1][j-1][0] + min(a[i-1],a[i+1]) - 1 ;
            f[i][j][0] = max(f[i-1][j][0],f[i-1][j][1]);
        }
    }

    for(int i=0;i<=k;i++)
        ans = max(ans,max(f[n][i][0],f[n][i][1]));

    printf("%lld",ans);

    return 0;
}