NC15553

題意

給你n個(gè)數(shù)，選2個(gè)長度為k的連續(xù)區(qū)間，求他們加起來的和最大為多少？

思路

前綴和預(yù)處理，然后利用前綴和計(jì)算k個(gè)數(shù)的最大數(shù)為多少，然后預(yù)處理從左邊遍歷到i為止最大的區(qū)間長度為k的和為多少，從右邊遍歷到i為止最大的區(qū)間長度為k的和為多少。
掃一遍要選的第一個(gè)區(qū)間，掃的過程如果左右還有可以選的區(qū)間，則取他們的最大值和選的區(qū)間相加，記錄最大值即可。

#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;
}

變形

一：不限制長度——在一個(gè)數(shù)列里找兩個(gè)不相交區(qū)間使得他們權(quán)值和最大
二：區(qū)間數(shù)目變多——找 {m}m個(gè)長度為 {k}k 的不相交區(qū)間使得他們的權(quán)值和最大
三：區(qū)間數(shù)目變多且不限制長度——找 {m}m 個(gè)不相交長度不限的區(qū)間使得他們權(quán)值和最大

思路

一：這題和原題的區(qū)別就是區(qū)間的長度不固定，顯然我們要選出兩個(gè)不相交的區(qū)間，且這兩個(gè)區(qū)間的和加起來要最大（這里要注意不一定是第一大的區(qū)間選出來再選一個(gè)剩下最大的區(qū)間，這樣他們的和不一定是最大的）。

二： 前綴和預(yù)處理
整體思想，把k個(gè)區(qū)間的和看為一個(gè)整體，表示到i個(gè)數(shù)為止拿j個(gè)區(qū)間的和

三：分兩種情況進(jìn)行DP（選還是不選第a[i]）。