题号 NC15553
名称 数学考试
来源 2018年长沙理工大学第十三届程序设计竞赛
链接：https://ac.nowcoder.com/acm/problem/15553
来源：牛客网
试题传送门
时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format:
%lld

题目描述
今天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 3
1 1 1 1 1 1
8 2
-1 0 2 -1 -1 2 3 -1

输出

6
7

题解：
题意就是求不想交的前缀与后缀和的最大值
第一反应是线段树（毕竟是有关区间查询 ） ，不过仔细想想也不能这么麻烦（打线段树不累吗？ ） ，不过也有大佬用线段树做的。
根据题意知道前缀与后缀长度一样，依据朴素的原则单纯打暴力肯定不行，需要优化优化，怎么优化呢？

我们先求出所有前缀和q[]
然后按照给定前后缀的长度k，求出每个k长区间的和
比如 -1 0 2 -1 -1 2 3 -1 k=2；
每个k长区间的和为：w[]-1 2 1 -2 1 5 2
我们所要求的最大值max=dp1+dp2
dp1是前缀和最大值
dp2是后缀和最大值
那其实就是在w中取一个dp1再取一个dp2，使他们和最大
但注意前缀与后缀不能相交和相连
方法一：
稍微处理下,可以先选后缀，然后前缀的范围就是去除已选的后缀，在里面取最大的前缀
maxx=(q[i]-q[i-k])+max(q[1],q[2],q[3].....q[i-k-1])
(q[i]-q[i-k])后缀和
max(q[1],q[2],q[3].....q[i-k-1])最大的前缀
然后求出maxx的最大值情况
诶，这不就是线性dp吗！wok做完才注意到
方法二：
求出前缀和所能取到的最大值（从头开始），放入数组w1
求出后缀和所能取到的最大值（从尾开始），放入w2中
然后再一个循环，求出w1[i]与w2[i+1]（即当前位i的前缀和与排在i之后的最大后缀和之和）的最大值
代码一

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
typedef long long ll;
using namespace std;
const int inf=2e5+4;
ll a[inf];
ll q[inf];
ll w[inf];
ll w1[inf],w2[inf];
int main()
{
  int t;
  cin>>t;
  int n,k;
  ll cnt;
  while(t--)
  {
          cin>>n>>k;
          for(int i=1;i<=n;i++)
          {
              cin>>cnt;
              q[i]=q[i-1]+cnt; 
        }
        memset(w1,-128,sizeof(w1));
            memset(w2,-128,sizeof(w2));
        cnt=-1e10;
        for(int i=k;i<=n;i++)
          {
              w[i]=q[i]-q[i-k];
        } 

        for(int i=k;i<=n;i++)
        {
                w1[i]=w[i]>w1[i-1]?w[i]:w1[i-1];
                if(i>=k)
                {
                    if(w[i]+w1[i-k]>cnt)cnt=w[i]+w1[i-k];
                }
        }



        cout<<cnt<<endl;
  }
  return 0;
}

代码二

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
typedef long long ll;
using namespace std;
const int inf=2e5+4;
ll a[inf];
ll q[inf];
ll w[inf];
ll w1[inf],w2[inf];
int main()
{
  int t;
  cin>>t;
  int n,k;
  ll cnt;
  while(t--)
  {
          cin>>n>>k;
          for(int i=1;i<=n;i++)
          {
              cin>>cnt;
              q[i]=q[i-1]+cnt; 
        }
        memset(w1,-128,sizeof(w1));
            memset(w2,-128,sizeof(w2));
        cnt=-1e10;
        for(int i=k;i<=n;i++)
          {
              w[i]=q[i]-q[i-k];
        } 

        for(int i=k;i<=n-k+1;i++)
            w1[i]=w[i]>w1[i-1]?w[i]:w1[i-1];


        for(int i=n-k+1;i>=k+1;i--)
            w2[i]=w2[i+1]>w[i+k-1]?w2[i+1]:w[i+k-1];

        for(int i=k;i<=n-k+1;i++)
        {
            if(w2[i+1]+w1[i]>cnt)cnt=w2[i+1]+w1[i];
        }
        cout<<cnt<<endl;
  }
  return 0;
}

对了有一点忘说了。。。不要忘记longlong，卡了我五分钟才发现
对了还有变形的问题：
（等晚上有空再想吧）