cf1826D

一个区间的权值为最大的三个数的和-区间长度，求最大的权值。

首先我们注意到，两个端点肯定是max，考虑反证法，假设当前选的是l,r区间，若两端不是max，则可以通过增大l，减小r来增加答案。（然而好像并没有什么用？）

我们可以设\(f[i][1/2/3]\)，表示到了第i个点，我们当前选了几个的最大贡献。那么根据dp的特点，对于一个区间，我们选出的肯定是最大的三个点，与题意符合。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
using namespace std;
const int N=1e5+5;
const int inf=2147483647;
int f[N][4],b[N],ans,n;
int main(){
//	freopen("data.in","r",stdin);
	int T;
	scanf("%d",&T);
	while (T--){
		ans=-inf;
		
		scanf("%d",&n);
		fo(i,1,n) scanf("%d",&b[i]);
		
		fo(i,1,n) {
			f[i][1]=f[i][2]=f[i][3]=-inf;
		}
	
		fo(i,1,n){
			f[i][1]=max(b[i]+i,f[i-1][1]);
			f[i][2]=max(b[i]+f[i-1][1], f[i-1][2]);
			f[i][3]=max(b[i]-i+f[i-1][2],f[i-1][3]);
			ans=max(ans,f[i][3]);
		}
		
		printf("%d\n",ans);
	}
	return 0;
}

没初始化wa了一发