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 的不相交区间使得他们的权值和最大
三：区间数目变多且不限制长度——找 {m}m 个不相交长度不限的区间使得他们权值和最大

思路

一：这题和原题的区别就是区间的长度不固定，显然我们要选出两个不相交的区间，且这两个区间的和加起来要最大（这里要注意不一定是第一大的区间选出来再选一个剩下最大的区间，这样他们的和不一定是最大的）。

二： 前缀和预处理
整体思想，把k个区间的和看为一个整体，表示到i个数为止拿j个区间的和

三：分两种情况进行DP（选还是不选第a[i]）。