题号 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;
}
对了还有变形的问题：
（等晚上有空再想吧）
京公网安备 11010502036488号