题目描述

今天qwb要参加一个数学考试，这套试卷一共有n道题，每道题qwb能获得的分数为ai，qwb并不打算把这些题全做完，
他想选总共2k道题来做，并且期望他能获得的分数尽可能的大，他准备选2个不连续的长度为k的区间,
即[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,...,R+k-1]（R >= L+k）。

题解

很明显题目就是让找两个长度为k，并且不相交的区间的最大和。
如果直接暴力枚举两个区间的端点来得到答案时间复杂度为O(n^2)显然不行
那么我们考虑怎样只枚举一个区间的端点，然后O(1)得到其他区间的最大值
显然是DP啦！！！
当我们枚举到i时，假设他所代表的的右区间为[i-k+1,i-k+2,....,i]，
那么就只需要知道1 ~ i-k中最大的字段和就可以了。
这一部分可以O(n)预处理出来，所以每个位置i的答案就为 f[i-k]+sum[i]-sum[i-k](f[i]为1 ~ i构成一个区间的最大值，sum[i]为ai的前缀和 )。
然后所有i取最大值就可以啦
要注意ai可能小于0，所以要把F数组初始化为负无穷

以下变形由于没有找到相应题目，仅供参考~

变形

1.考虑只有一个区间，长度不限的求法(这是一个经典模型)。

设dp[i]为以i为结尾的最大值 ，所以 dp[i]=max(dp[i-1]+a[i],a[i]),求出dp数组后数组中最大的值就是答案
如果会了上面的话，求两个区间的话似乎也不是很难了。考虑到最后的两个区间是被隔开的，假设是被i，那么我们只需要求出i之前构成一个区间的最大值和i之后构成一个区间的最大值(这部分参考求一个区间的情况，只需正向dp一下取max，反向dp一下取maxjiu'ke)，取和。那么被i隔开的情况就求出来了。
然后在枚举i就可以得到所有的情况。时间复杂度O(n)

2区间数目变多——找 {m}m个长度为 {k}k 的不相交区间使得他们的权值和最大 (1≤n≤5000)

还是dp，令dp[i][j]表示前i个数字构成j个不相交区间的最大值后dp[n][k]即为所求
转移方程：dp[i][j]=min{dp[i-k][j-1]+sum[i]-sum[i-k]} 复杂度O(n*k)

三：区间数目变多且不限制长度——找 {m}m 个不相交长度不限的区间使得他们权值和最大(1≤n≤5000)

这种情况，我想了几种方法都不是很优秀，所以一起期待其他大佬的题解吧！！

#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;


const int N = 5e3+5;
const int mod =1e9+7;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6+6;

int _,n,k;
LL a[maxn],f[maxn];

int main(){
    for(scanf("%d",&_);_;_--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]+=a[i-1];
        for(int i=1;i<k;i++) f[i]=-inf;
        for(int i=k;i<=n;i++) f[i]=max(f[i-1],a[i]-a[i-k]);

        LL ans=-inf;
        for(int i=2*k;i<=n;i++){
            ans=max(ans,a[i]-a[i-k]+f[i-k]);
        }
        printf("%lld\n",ans);
    }
}