【Luogu P1121】環狀最大兩段子段和

題目連結

題目描述

給出一段環狀序列，即認為A[1]和A[N]是相鄰的，選出其中連續不重疊且非空的兩段使得這兩段和最大。

(N≤2×105) ( N ≤ 2 × 10 5 )

題解

我相信大多數人第一眼看到這道題的想法就是破環成鍊。

但是一看資料範圍N到了 10^5 ，那麼你枚舉斷點就已經有O(n)的複雜度了，轉移想要做到log什麼的不太可能。

不妨先來看沒有環的，一種做法就是預處理從前向後與從後向前記錄到達每一個點的最大子段，再枚舉斷點把兩端接起來。

另一種方法就是dp了，我們設 dp[0/1/2/3/4][N] d p [ 0 / 1 / 2 / 3 / 4 ] [ N ] 表示到N的時候 還沒選/在選第一段/選完了第一段/在選第二段/選完了第二段 的最大和 轉移即可。

其實鍊狀做法的唯一不能出理的情況便是首位相接的，并且這算一段。

那麼我們隻需要強制選擇首尾即可。

具體來說就是重新設 f[0/1/2/3/4][N],g[0/1/2/3/4][N] f [ 0 / 1 / 2 / 3 / 4 ] [ N ] , g [ 0 / 1 / 2 / 3 / 4 ] [ N ] 表示到N時的狀态，但g是從後往前dp的，并且都強制選擇最前面一段即可。

P.S. : 環狀問題要麼 破換成鍊 要麼 分類讨論 。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
#define Set(a,b) memset(a,b,sizeof(a))
using namespace std;
inline int read()
{
    int x=;char ch=getchar();int t=;
    for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=-;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<)+(x<<)+(ch-);
    return x*t;
}
const int N=+;
int a[N];
int dp[][N];
int f[][N],g[][N];
int n;
const int INF=;
int main()
{
    n=read();
    Set(dp,-/);Set(f,-/);Set(g,-/);
    register int sum=;int ans=-INF;
    for(register int i=;i<=n;++i) {
        a[i]=read();sum+=a[i];
        dp[][i]=;dp[][i]=max(a[i],dp[][i-]+a[i]);
        dp[][i]=max(dp[][i-],dp[][i-]);dp[][i]=max(dp[][i-]+a[i],dp[][i-]+a[i]);
        ans=max(ans,dp[][i]);
        f[][i]=sum;f[][i]=max(f[][i-],f[][i-]);f[][i]=max(f[][i-],f[][i-])+a[i];
        f[][i]=max(f[][i-],f[][i-]);
    }
    sum=;
    for(register int i=n;i;--i)
    {
        sum+=a[i];
        g[][i]=sum;g[][i]=max(g[][i+],g[][i+]);g[][i]=max(g[][i+],g[][i+])+a[i];
        g[][i]=max(g[][i+],g[][i+]);
    }
    ans=max(ans,sum);
    for(register int i=;i<n;++i)
    {
        register int mf=max(f[][i],f[][i]),mg=g[][i];
        ans=max(ans,max(max(mf+mg,mf+g[][i]),max(f[][i]+g[][i],f[][i]+mg)));
    }
    printf("%d\n",ans);
}