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

题目描述

如果数组

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

。

代码

CPP

#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;
}

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

文章操作

题目描述

输入格式

输出格式

题解

代码

相关推荐

评论

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