NC15553

题意

给你n个数，选2个长度为k的连续区间，求他们加起来的和最大为多少？

思路

前缀和预处理，然后利用前缀和计算k个数的最大数为多少，然后预处理从左边遍历到i为止最大的区间长度为k的和为多少，从右边遍历到i为止最大的区间长度为k的和为多少。
扫一遍要选的第一个区间，扫的过程如果左右还有可以选的区间，则取他们的最大值和选的区间相加，记录最大值即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 2e5 + 5;

ll a[maxn],s[maxn],L[maxn],R[maxn];

int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int T;cin>>T;
	while(T--){
		ll n,k;
		cin>>n>>k;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			s[i]=s[i-1]+a[i];
			L[i]=-1e18,R[i]=-1e18;
		}
		for(int i=k;i<=n-k;i++){
			L[i]=max(L[i-1],s[i]-s[i-k]);
		}
		for(int i=n-k+1;i>=k+1;i--){
			R[i]=max(R[i+1],s[i+k-1]-s[i-1]);
		}
		ll res=-1e18;
		for(int i=k;i<=n-k;i++){
			res=max(res,L[i]+R[i+1]);
		}
		cout<<res<<'\n';
	}
	return 0;
}

变形

一：不限制长度——在一个数列里找两个不相交区间使得他们权值和最大
二：区间数目变多——找 {m}m个长度为 {k}k 的不相交区间使得他们的权值和最大 $(1\le n\le 50001\le n\le 5000)$(1≤n≤50001≤n≤5000)
三：区间数目变多且不限制长度——找 {m}m 个不相交长度不限的区间使得他们权值和最大 $(1\le n\le 50001\le n\le 5000)$(1≤n≤50001≤n≤5000)

思路

一：这题和原题的区别就是区间的长度不固定，显然我们要选出两个不相交的区间，且这两个区间的和加起来要最大（这里要注意不一定是第一大的区间选出来再选一个剩下最大的区间，这样他们的和不一定是最大的）。
$L\left[i\right]=\left(\right(L[i-1]>0)?L[i-1]:0)+a\left[i\right]必须选i的情况下左边这段最大的值R\left[i\right]=\left(\right(R[i+1]>0)?R[i+1]:0)+a\left[i\right]必须选i的情况下右边这段最大的值mL\left[i\right]=max\left(mL\right[i-1],L[i\left]\right)到第i号元素为止左边的最大值mR\left[i\right]=max\left(mR\right[i+1],R[i\left]\right)到第i号元素为止右边的最大值$L[i]=((L[i−1]>0)?L[i−1]:0)+a[i]必须选i的情况下左边这段最大的值R[i]=((R[i+1]>0)?R[i+1]:0)+a[i]必须选i的情况下右边这段最大的值mL[i]=max(mL[i−1],L[i])   到第i号元素为止左边的最大值mR[i]=max(mR[i+1],R[i])   到第i号元素为止右边的最大值

二： $DP$DP 前缀和预处理
整体思想，把k个区间的和看为一个整体， $f\left[i\right]\left[j\right]$f[i][j]表示到i个数为止拿j个区间的和
$f\left[i\right]\left[j\right]=max\left(f\right[i-k\left]\right[j-1]+sum[i]-sum[i-k],f[i-1\left]\right[j\left]\right)$f[i][j]=max(f[i−k][j−1]+sum[i]−sum[i−k],f[i−1][j])

三：分两种情况进行DP（选还是不选第a[i]）。
$f\left[i\right]\left[j\right]\left[0\right]=max\left(f\right[i-1\left]\right[j\left]\right[0],f[i-1\left]\right[j\left]\right[1\left]\right)f\left[i\right]\left[j\right]\left[1\right]=max\left(f\right[i-1\left]\right[j\left]\right[1],f[i-1\left]\right[j-1\left]\right[0],f[i-1\left]\right[j-1\left]\right[1\left]\right)+a\left[i\right]$f[i][j][0]=max(f[i−1][j][0],f[i−1][j][1])f[i][j][1]=max(f[i−1][j][1],f[i−1][j−1][0],f[i−1][j−1][1])+a[i]