P1121 环状最大两段子段和
题目描述
给出一段环状序列，即认为\(A_1\)和\(A_N\)是相邻的，选出其中连续不重叠且非空的两段使得这两段和最大。
输入输出格式
输入格式：
第一行是一个正整数\(N(N≤2×10^5)\) ，表示了序列的长度。
第二行包含\(N\)个绝对值不大于10000的整数\(A_i\)，描述了这段序列，第一个数和第\(N\)个数是相邻的。
输出格式：
一个整数，为最大的两段子段和是多少。
最开始想的倍增优化，感觉其实好像也可以做，但写起来复杂到毁天灭地。
于是听教练讲了\(O(n)\)的做法。
先考虑单链情况。
对于这个序列，我们首先划分它的状态
其中\(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\)三段
不就是把环连起来了吗
于是问题就转化到了找最小两段子段和上，做法是一样的。
不过需要注意的是，最小子段和不能两端同时取到端点，否则就是单段最大子段和了。
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