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