Luogu1121：环状最大两段子段和

题面

传送门

Sol

两种情况

第一种就是类似\(***000***000***(0表示选)\)，这个可以DP

设\(h[0/1/2/3][i]\)表示到第\(i\)位的状态：

\(0\):表示还没选

\(1\):表示当前在第一段

\(2\):表示选完了第一段

\(3\):表示当前在第二段

第二种就是类似\(000****000***000\)，这个也可以DP

设\(f[0/1/2/3][i]\)表示到第\(i\)位的状态：要强制选左边

\(0\):表示目前在第一段

\(1\):表示第一段选完

\(2\):表示目前在第二段

\(3\):表示第二段选完

设\(g[0/1/2/3][i]\)从后往前，强制选右边

\(f和g\)拼起来就好了

# include <bits/stdc++.h>

# define IL inline

# define RG register

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

const int _(2e5 + 5);

IL ll Read(){

    RG char c = getchar(); RG ll x = 0, z = 1;

    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

    return x * z;

}

ll n, a[_], f[4][_], g[4][_], ans = -1e18, h[4][_];

int main(RG int argc, RG char* argv[]){

	n = Read(); Fill(f, -63); Fill(g, -63); Fill(h, -63);

	for(RG int i = 1; i <= n; ++i) a[i] = Read();

	f[0][0] = g[0][n + 1] = h[0][0] = 0;

	for(RG int i = 1; i <= n; ++i){

		f[0][i] = f[0][i - 1] + a[i];

		f[1][i] = max(f[0][i], f[1][i - 1]);

		f[2][i] = max(f[1][i - 1], f[2][i - 1]) + a[i];

		f[3][i] = max(f[2][i], f[3][i - 1]);

		h[0][i] = h[0][i - 1];

		h[1][i] = max(h[0][i - 1], h[1][i - 1]) + a[i];

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

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

		ans = max(ans, h[3][i]);

	}

	for(RG int i = n; i; --i){

		g[0][i] = g[0][i + 1] + a[i];

		g[1][i] = max(g[0][i], g[1][i + 1]);

		g[2][i] = max(g[2][i + 1], g[1][i + 1]) + a[i];

		g[3][i] = max(g[2][i], g[3][i + 1]);

	}

	for(RG int i = 1; i < n; ++i){

		ans = max(ans, f[3][i] + g[1][i + 1]);

		ans = max(ans, f[1][i] + g[3][i + 1]);

	}

	printf("%lld\n", ans);

	return 0;

}