洛谷 P1121 环状最大两段子段和 解题报告

时间:2022-07-08 10:39:22

P1121 环状最大两段子段和

题目描述

给出一段环状序列,即认为\(A_1\)和\(A_N\)是相邻的,选出其中连续不重叠且非空的两段使得这两段和最大。

输入输出格式

输入格式:

第一行是一个正整数\(N(N≤2×10^5)\) ,表示了序列的长度。

第二行包含\(N\)个绝对值不大于10000的整数\(A_i\),描述了这段序列,第一个数和第\(N\)个数是相邻的。

输出格式:

一个整数,为最大的两段子段和是多少。


最开始想的倍增优化,感觉其实好像也可以做,但写起来复杂到毁天灭地。

于是听教练讲了\(O(n)\)的做法。

先考虑单链情况。

对于这个序列,我们首先划分它的状态

洛谷 P1121 环状最大两段子段和 解题报告

其中\(S1\)区和\(S3\)区是选中的两段。

不妨就把这些划分为\(dp\)的状态。

令\(dp[i][j]\)代表在长度\(i\)时处于\(j\)区的最大答案

状态转移:

\(dp[i][0]=max(dp[i-1][0],dp[i-1][3]);\)

\(dp[i][1]=max(dp[i-1][4],dp[i-1][1])+a[i];\)

\(dp[i][2]=max(dp[i-1][1],dp[i-1][2]);\)

\(dp[i][3]=max(max(dp[i-1][2],dp[i-1][1]),dp[i-1][3])+a[i];\)

\(dp[i][4]=dp[i-1][4];\)

容易发现,\(dp[i][4]\)总是0,遂可以扔掉这一维。

解决了单链的,我们想一想如果推广到环上。一般的方法是延长链为两倍,但这个并不是区间\(dp\),所以很难限定区间。

这里提供一种类似于费用提前的做法。

还是这张图,假设选取了\(s0,s2,s4\)三段

洛谷 P1121 环状最大两段子段和 解题报告

不就是把环连起来了吗

于是问题就转化到了找最小两段子段和上,做法是一样的。

不过需要注意的是,最小子段和不能两端同时取到端点,否则就是单段最大子段和了。


code:

#include <cstdio>
#include <cstring>
int min(int x,int y) {return x<y?x:y;}
int max(int x,int y) {return x>y?x:y;}
const int N=200010;
const int inf=0x3f3f3f3f;
int a[N],dp[N][4],n,ans=-inf,sum=0;//0不选右,1左段,2中间不选,3右段
void dp1()
{
memset(dp,-0x3f,sizeof(dp));
dp[1][1]=a[1];
for(int i=2;i<=n;i++)
{
dp[i][0]=max(dp[i-1][0],dp[i-1][3]);
dp[i][1]=max(0,dp[i-1][1])+a[i];
dp[i][2]=max(dp[i-1][1],dp[i-1][2]);
dp[i][3]=max(max(dp[i-1][2],dp[i-1][1]),dp[i-1][3])+a[i];
}
ans=max(dp[n][0],dp[n][3]);
}
void dp2()
{
memset(dp,0x3f,sizeof(dp));
dp[1][1]=a[1];
for(int i=2;i<=n;i++)
{
dp[i][0]=min(dp[i-1][0],dp[i-1][3]);
dp[i][1]=min(0,dp[i-1][1])+a[i];
dp[i][2]=min(dp[i-1][1],dp[i-1][2]);
dp[i][3]=min(min(dp[i-1][1],dp[i-1][2]),dp[i-1][3])+a[i];
}
ans=max(ans,sum-dp[n][0]);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
sum+=a[i];
}
dp1();
dp2();
printf("%d\n",ans);
return 0;
}

2018.6.6