【每日一题】3月27日题目精讲 前缀和、动态规划

题目描述

今天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）。

输入描述:

第一行一个整数T（T<=10）,代表有T组数据
接下来一行两个整数n,k,(1<=n<=200,000),(1<=k,2k <= n)
接下来一行n个整数a1,a2,...,an，（-100,000<=ai<=100,000）

输出描述:

输出一个整数，qwb能获得的最大分数

示例1

2
6 3r33
1 1 1 1 1 1
8 2
-1 0 2 -1 -1 2 3 -1

输出

6
7

题解

因为长度已知，最暴力的办法肯定是直接枚举两个子区间的起点，然后求和，复杂度，求和可以用前缀和来优化，即用 sum[i]表示数列前 i 个数字的和，那么sum[i]=sum[i−1]+a[i]，而区间[l,r] 的和则可以表示为sum[r]−sum[l−1]。这样优化之后就不用遍历求和了直接算就好，时间复杂度变为。

实际上我们根本不用枚举右边子区间的起点，因为如果我们的选择的左边这个区间是[l,r] 的话，右边的区间一定是 r 右边的所以长度为 k 的区间里面和最大的那个，这个只需要从右往左扫描一遍就可以维护出来——如果我们用 right[i] 表示 i 右边的所有长度为 k 的区间的和的最大值，那么right[i]=max(right[i+1],sum[i+k−1]−sum[i−1])（要么是i+1右边长度为 k 的区间的最大值，要么是从 i 开始向右长度为 k 的区间）。
这样子了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef pair<int,int> PII;
typedef long long LL;
const int INF=0x3f3f3f3f;
const LL IINF=0x3f3f3f3f3f3f3f3f;

const int N=2e5+10;
int v[N];
LL sum[N];
LL f1[N];
LL f2[N];
int n,k;

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(f1,-0x3f,sizeof f1);
        memset(f2,-0x3f,sizeof f2);

        cin>>n>>k;

        for(int i=1;i<=n;i++)
        {
            cin>>v[i];
            sum[i]=sum[i-1]+v[i];
        }

        for(int i=k;i<=n;i++)
            f1[i]=max(f1[i-1],sum[i]-sum[i-k]);
        for(int i=n-k+1;i>=1;i--)
            f2[i]=max(f2[i+1],sum[i+k-1]-sum[i-1]);
        LL ans=-IINF;
        for(int i=k;i<=n-k;i++)
            ans=max(ans,f1[i]+f2[i+1]);
        cout<<ans<<endl;
    }

    // system("pause");
}

变形一

不限制长度——在一个数列里找两个不相交区间使得他们权值和最大

如果思路还和刚刚一样，如果我们用 right[i] 表示 i 右边的所有子区间的和的最大值的话right[i]=max(right[i+1],sum[j]−sum[i−1])(i<j)，显然如果要让sum[j]−sum[i−1]尽量大，j一定会取 sum[j] 最大的那个，所以再维护一个数组 maxsum[i] 表示 i 之后sum的最大值即可。

但是这样的话你会发现由于区间的长度不固定了，我们在枚举左区间的时候是需要枚举两个端点的，复杂度又回到了，事实上这也不需要，我们其实只需要枚举左右区间的分界点，即用另外一个数组维护一个 i 左边所有子区间的最大值（这个过程和上述过程是对称的），然后分界点左右区间最大值相加即可。

另外，维护 i 右边的所有子区间的和的最大值还有一种办法，使用动态规划的思想——用f[i]表示必须要选i的情况下i向右最大的区间和，f[i]=max(a[i],a[i]+f[i+1])，然后right[i]=max(f[i],right[i+1])。

变形二

区间数目变多——找 m个长度为 k 的不相交区间使得他们的权值和最大

这个时候就必须要上动态规划了。
f[i][j] 表示前 i 个数已经选了 j 个长度为 k 的不相交区间的最大权值和
每次转移我们只需要考虑第 i 数个选还是不选，要选它就要选它以前的 k-1 个数构成一个连续的 k 个数的区间；不选它，那扔掉就好。

变形三

区间数目变多且不限制长度——找 m 个不相交长度不限的区间使得他们权值和最大

有了前一个题的经验，我们还是用f[i][j]表示前 i个数里已经选了 j个不相交区间的最大权值和，还是考虑第 i 个选不选。

这个时候一个小问题出现了，如果我们要选 a[i]，选中的区间数究竟是会+1呢还是不变呢？也就是说，我们不知道第 i-1 个数选没选所以没法转移……那怎么办？我们在状态的描述中强行规定 f[i][j] 表示第 i 个数必须要选且前 i 个数里已经选了 j 个不相交区间的最大权值和，既然第 i 个数必须要选了，那么f[i][j]=max(f[i−1][j]+a[i],f[p][j−1]+a[i]),p<i 即 a[i] 可以接在上一个区间后面，或者成为一个区间的第一个元素。

还是刚刚那个问题，我们并不想要枚举 p，而这个式子含有 p 的部分也正好是f数组上一列的一个从1 开始的连续区间的最大值，i 加 1 的时候 p 也相应加一，所以对上一列求一个前缀最大值即可。即我们在转移的时候维护一个数组maxx[i][j]表示 {f}f 数组第 j 列前 i 个数的最大值，即所有的满足的f[k][j]的最大值 。所以f[i][j]=max(f[i−1][j]+a[i],maxx[i−1][j−1]+a[i]), p 这里有一个小技巧：当状态转移方程中等式右边包含一个区间的最值，且这个是区间一个端点固定另一个端点随着转移而递增的，就可以用前缀最值来维护，同样的情况，如果是求和，就用前缀和来维护。对于学有余力的同学，这个技巧还可以扩展：如果是一个等式右边是一个定长连续区间的最值，那么是可以用单调队列的来维护的。

另一种解法：
设g[i][j][0/1] 表示前 i 个数，分成 j 段，第 i个不选/选的最大值，转移方程：
g[i][j][0]=max(g[i−1][j][0],g[i−1][j][1])
g[i][j][1]=max(g[i−1][j][1],g[i−1][j−1][1],g[i−1][j−1][0])+a[i]
就没有之前的需要求前缀最大值的问题了

因为在上面的所有的max(f[p][j−1]+a[i]) 中 除了f[i−1][j−1]+a[i] ，其他的所有情况就是前 i-1 个数分成 j 段，第 i-1个不选的最大值，也就是g[i−1][j−1][0]的值，换句话说 max(g[i−1][j−1][1],g[i−1][j−1][0]+a[i]，这一部分其实就是上面的max(f[p][j−1]+a[i])，g[i−1][j−1][0]就是上面那个前缀最大值的一部分。

实际上，这位同学的状态才是这个问题严谨而完整的状态，二维状态，f[i][j]表示第 i 个数必须选的情况下前 i 个数里已经选了 j 个的不相交区间的最大权值和时，实际上是将不选i的情况省略掉了，这种省略有的时候是可以省掉可算可不算的部分，但是在这个问题里，显然这种省略其实反而使得转移的时候麻烦了起来。