2021牛客OI赛前集训营-提高组（第三场） T1变幻

2021牛客OI赛前集训营-提高组（第三场）

题目大意

对于一个大小为$n$的数组$a$的任意一点$i$，若满足$a_{i-1}>a_i$且$a_i<a_{i+1}$，则称$i$为山谷点。$1$和$n$不可能为山谷点。

你最多可以修改最多$k$次数组，每次可以将一个$a_i$的值变小。

求所有山谷点的$a$值之和的最大值。

题解

设$f_{i,j}$表示最后一次修改在点$i$或点$i$之前，已经修改了$j$次的前$i$个数的最大的山谷点的和，那么

• $f_{i,j}=f_{i-1,j}$
• 如果$a_i$本来就是山谷点，则$f_{i,j}=\max (f_{i,j},f_{i-2,j}+a_i)$
• 如果$j\ge 1$，则$f_{i,j}=\max (f_{i,j},f_{i-2,j-1}+\min (a_{i-1},a_{i+1})-1)$

答案为$\underset{i=0}{\overset{k}{\max }}{f}_{n-1,i}$。

时间复杂度为$O(nk)$。

code

#include<bits/stdc++.h>
using namespace std;
int n,k;
long long ans=0,a[2005],f[2005][2005];
int main()
{scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}for(int i=1;i<=n;i++){for(int j=0;j<=n;j++) f[i][j]=-1e18;}f[1][0]=0;for(int i=2;i<n;i++){for(int j=0;j<=k;j++){f[i][j]=f[i-1][j];if(a[i]<a[i-1]&&a[i]<a[i+1]) f[i][j]=max(f[i][j],f[i-2][j]+a[i]);else if(j>=1) f[i][j]=max(f[i][j],f[i-2][j-1]+min(a[i-1],a[i+1])-1);}}for(int i=0;i<=k;i++) ans=max(ans,f[n-1][i]);printf("%lld",ans);return 0;
}