建设项目验收网站跨境电商seo
2021牛客OI赛前集训营-提高组（第三场）
题目大意
对于一个大小为nnn的数组aaa的任意一点iii，若满足ai−1>aia_{i-1}>a_iai−1>ai且ai<ai+1a_i<a_{i+1}ai<ai+1，则称iii为山谷点。111和nnn不可能为山谷点。
你最多可以修改最多kkk次数组，每次可以将一个aia_iai的值变小。
求所有山谷点的aaa值之和的最大值。
题解
设fi,jf_{i,j}fi,j表示最后一次修改在点iii或点iii之前，已经修改了jjj次的前iii个数的最大的山谷点的和，那么
- fi,j=fi−1,jf_{i,j}=f_{i-1,j}fi,j=fi−1,j
- 如果aia_iai本来就是山谷点，则fi,j=max(fi,j,fi−2,j+ai)f_{i,j}=\max(f_{i,j},f_{i-2,j}+a_i)fi,j=max(fi,j,fi−2,j+ai)
- 如果j≥1j\geq 1j≥1，则fi,j=max(fi,j,fi−2,j−1+min(ai−1,ai+1)−1)f_{i,j}=\max(f_{i,j},f_{i-2,j-1}+\min(a_{i-1},a_{i+1})-1)fi,j=max(fi,j,fi−2,j−1+min(ai−1,ai+1)−1)
答案为maxi=0kfn−1,i\max\limits_{i=0}^kf_{n-1,i}i=0maxkfn−1,i。
时间复杂度为O(nk)O(nk)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;
}