这题乍一看还挺简单的，仔细一看，好像还有那么点意思。
题意：
从n个数中选出两个不相交的区间，且区间长度都为K，求这两个区间的和的最大值。(n<=200000)
题目类型：
前缀和、动态规划、线段树
思路：
由于区间长度是固定的，很容易想到枚举区间的起点。如果分别枚举两个区间的起点的话，我们需要O(n^2)复杂度，中间的求和可以通过预处理前缀和获得，但是显然会超时。
我一开始的做法是，预处理出所有长度为K的区间和，然后丢进线段树里。接着枚举其中一个区间的起点，那么剩下的一个区间的最大值直接从线段树里去查就好了，这样的话O(nlogn)就可以解决。嗯，写起来还是比较快的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200040;
const ll inf=3e10;
int n,k;
ll a[maxn],sum[maxn],sumk[maxn]; //sum[]表示前缀和，sumk[]表示长度为k的区间和
void init(){
sum[0]=0;
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
for(int i=1;i<=n-k+1;i++){
sumk[i]=sum[i+k-1]-sum[i-1];
}
}
struct node{
int l,r;
ll maxi;
}tree[maxn<<2];
void build(int l,int r,int rt){
tree[rt].l=l;
tree[rt].r=r;
if(l==r){
tree[rt].maxi=sumk[l];
return;
}
int mid=l+r>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
tree[rt].maxi=max(tree[rt<<1].maxi,tree[rt<<1|1].maxi);
}
ll query(int l,int r,int rt){
if(l>r)return -inf;
if(l==tree[rt].l&&r==tree[rt].r){
return tree[rt].maxi;
}
int mid=tree[rt].l+tree[rt].r>>1;
if(mid>=r)return query(l,r,rt<<1);
else if(l>mid)return query(l,r,rt<<1|1);
else return max(query(l,mid,rt<<1),query(mid+1,r,rt<<1|1));
}
int main()
{
int t;
cin>>t;
while(t--){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
init();
build(1,n-k+1,1);
ll maxians=-inf;
for(int i=1;i<=n-k+1;i++){
ll b1,b2;
b1=sumk[i];
b2=max(query(1,i-k,1),query(i+k,n-k+1,1));
maxians=max(maxians,b1+b2);
}
cout<<maxians<<endl;
}
return 0;
}题解中提供了一种线性做法，代码更加简洁而且速度更快。
我们可以将两个区间分成左右两个，我们可以从右往左枚举左边区间的起点，右边区间的起点我们可以不需要枚举了，直接在过程中进行维护就可以。
根据这个思路，我写了一个类似尺取法的代码。过程中维护右边区间的最大和。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200040;
const ll inf=3e10;
int n,k;
ll a[maxn],sum[maxn],sumk[maxn];
void init(){
sum[0]=0;
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
for(int i=1;i<=n-k+1;i++){
sumk[i]=sum[i+k-1]-sum[i-1];
}
}
int main()
{
int t;
cin>>t;
while(t--){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
init();
ll maxians=sumk[n-2*k+1]+sumk[n-k+1];
//cout<<"*******"<<maxians<<endl;
int l,r;
l=n-k;r=n;
ll t1,t2,tmp;
t2=tmp=sumk[n-k+1];
for(int i=n-2*k;i>=1;i--){
t1=sumk[i];
t2=max(t2,tmp=tmp-a[r--]+a[l--]);
maxians=max(maxians,t1+t2);
}
cout<<maxians<<endl;
}
return 0;
}当然也可以用一个数组来记录，令maxr[i]表示从i开始的所有长度为K的区间中的最大和。
那么我们可以得到一个转移方程,maxr[i]=max(maxr[i+1],sum[i+k-1]-sum[i-1])。这样一来，线性时间就解决了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200040;
const ll inf=3e10;
int n,k;
ll a[maxn],sum[maxn],sumk[maxn],maxr[maxn];
void init(){
sum[0]=0;
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
for(int i=1;i<=n-k+1;i++){
sumk[i]=sum[i+k-1]-sum[i-1];
}
}
int main()
{
int t;
cin>>t;
while(t--){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
init();
ll maxians=-inf;
maxr[n-k+1]=sum[n]-sum[n-k];
for(int i=n-k;i>=1;i--){
maxr[i]=max(maxr[i+1],sum[i+k-1]-sum[i-1]);
}
for(int i=1;i<=n-2*k+1;i++){
ll t1,t2;
t1=sumk[i];
t2=maxr[i+k];
maxians=max(maxians,t1+t2);
}
cout<<maxians<<endl;
}
return 0;
}接着，题解中提出了3个变式，都是值得思考。
给大家提出几个变形的相关问题：
一：不限制长度——在一个数列里找两个不相交区间使得他们权值和最大
二：区间数目变多——找 m个长度为 k 的不相交区间使得他们的权值和最大 ( 1≤n≤5000)
三：区间数目变多且不限制长度——找 m 个不相交长度不限的区间使得他们权值和最大( 1≤n≤5000)
首先是变形一：
利用原题的思路，我们可以得到maxr[i]表示从i开始往右的区间和中的最大值，同样的我们可以用maxl[i]表示从i开始往左的区间和中的最大值。然后要找两个不相交区间的权值和最大，只要枚举左右两个区间的分界点就好了。复杂度也是O（n）。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5040;
const ll inf=3e10;
int n,k;
ll a[maxn],sum[maxn],maxl[maxn],maxr[maxn],dp1[maxn],dp2[maxn];
void init(){
sum[0]=0;
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
}
int main()
{
int t;
cin>>t;
while(t--){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
init();
for(int i=1;i<=n;i++){
dp1[i]=max(dp1[i-1]+a[i],a[i]);
}
for(int i=n;i>=1;i--){
dp2[i]=max(dp2[i+1]+a[i],a[i]);
}
for(int i=n;i>=1;i--){
maxr[i]=max(maxr[i+1],dp2[i]);
}
for(int i=1;i<=n;i++){
maxl[i]=max(maxl[i-1],dp1[i]);
}
ll maxians=0;
for(int i=2;i<n;i++){
maxians=max(maxians,max(maxl[i]+maxr[i+1],maxl[i-1]+maxr[i]));
}
cout<<maxians<<endl;
}
return 0;
}变形二：
现在需要找m个区间长度为K的不相交区间的最大权值和。
这个问题其实就是分组问题，令dp[i][j]表示前i个数已经分了j组的最大权值和。
对于当前第i个数，若选择他，注意我们在进行dp维护的时候要保证已经分了j组了，所以我们可以获得的转移方程式：dp[i][j]=dp[i-k][j-1]+sum[i]-sum[i-k]。也就是说，a[i]刚好成为j组的最后一个，那么我们自然从dp[i-k][j-1]转移过来了。
若不选择a[i]，显然我们有dp[i][j]=dp[i-1][j]
因此两个里面取大的那个就好了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5040;
const ll inf=3e10;
int n,k,m;
ll a[maxn],sum[maxn],dp[maxn][maxn];
void init(){
sum[0]=0;
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
for(int i=0;i<maxn;i++){
for(int j=0;j<maxn;j++)dp[i][j]=-inf;
}
for(int i=0;i<maxn;i++)dp[i][0]=0;
}
int main()
{
int t;
cin>>t;
while(t--){
cin>>n>>m>>k; //n个数m组,每组k个
for(int i=1;i<=n;i++)cin>>a[i];
init();
for(int i=1;i<=n;i++){
for(int j=1;j<=min(m,i/k);j++){
dp[i][j]=max(dp[i-1][j],dp[i-k][j-1]+sum[i]-sum[i-k]);
}
}
//for(int i=1;i<=n;i++)cout<<dp[i][m]<<endl;
cout<<dp[n][m]<<endl;
}
return 0;
}
/*
2
8 3 2
1 -1 2 3 4 -9 8 5
6 2 2
2 3 -4 5 7 -8
*/变形三：
如果不限长度，不限数量。
参考变形二，我们可以得到dp[i][j]表示前i个数分j组的最大和。
显然，此刻我们按照选或不选的方式去转移，选择a[i]的时候，我们发现无法进行转移了：因为长度不确定，所以无法判断从哪里过来了。
这里我们修改一下dp状态，令dp[i][j]表示前i个数分j组并且i强制选择的最大和。
此时我们可以知道，dp[i][j]有两种情况，第一种是和前面连续，dp[i][j]=dp[i-1][j]+a[i]
第二种是a[i]单独一个新区间，dp[i][j]=dp[k][j-1]+ai
好了dp[k][j-1]中的k是需要枚举的，但我们可以发现k和i时同步增加的，因此我们维护一个maxp[i][j]前缀和数组，表示1-i中分j组的最大值。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5040;
const ll inf=3e10;
int n,k,m;
//maxp[i]表示1-i中分j组的最大值
ll a[maxn],sum[maxn],dp[maxn][maxn],maxp[maxn][maxn];
void init(){
sum[0]=0;
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
for(int i=0;i<maxn;i++){
for(int j=0;j<maxn;j++)dp[i][j]=maxp[i][j]=-inf;
}
for(int i=0;i<maxn;i++)dp[i][0]=0;
}
int main()
{
int t;
cin>>t;
while(t--){
cin>>n>>m; //n个数m组,每组不限
for(int i=1;i<=n;i++)cin>>a[i];
init();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
maxp[i-1][j-1]=max(maxp[i-2][j-1],dp[i-1][j-1]);
dp[i][j]=max(dp[i-1][j]+a[i],maxp[i-1][j-1]+a[i]);
}
}
// cout<<maxp[1][1]<<' '<<maxp[2][1]<<endl;
ll maxians=-inf;
for(int i=1;i<=n;i++)maxians=max(maxians,dp[i][m]);
cout<<maxians<<endl;
}
return 0;
}
/*
2
8 3 2
1 -1 2 3 4 -9 8 5
6 2 2
2 3 -4 5 7 -8
*/更进一步地，可以将dp状态定义为dp[i][j][0/1]表示前i个分成j组且第i个取或不取的状态。
这样一来，状态转移更加清晰：
dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1])
dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][1],dp[i-1][j-1][0])+a[i]
果然很多时候dp多一维状态表示可以简化很多思考过程和转移过程。
这中间的dp状态定义和转移，以及优化的思考过程，还可以好好的挖掘~
京公网安备 11010502036488号