数列 \(D_{i, j}\) を以下のように定めます。

• \(D_{i, 1} = \displaystyle\sum_{j = 1}^{i} A_j\)
• \(D_{i, 2} = \displaystyle\max_{1 \leq x < i}(\sum_{j =1} ^ {x} A_j + \sum_{j = x + 1}^{i} B_j)\)
• \(D_{i, 3} = \displaystyle\max_{1 \leq x < y < i}(\sum_{j =1} ^ {x} A_j + \sum_{j = x + 1}^{y} B_j + \sum_{j =y + 1} ^ {i} C_j)\)

求める答えは \(D_{N, 3}\) です。

ここで、\(D_{i, j}\) たちは動的計画法の要領で計算できます。具体的には、\(D_{i - 1, *}\) たちの値と \(A_i, B_i, C_i\) の値から \(D_{i, *}\) を計算することができます。\(i\) 番目の要素として \(A_i, B_i, C_i\) のどれを和に寄与させるかで場合分けを行うことで、以下の遷移により計算できることがわかります。

• \(D_{i, 1} = D_{i - 1, 1} + A_i\)
• \(D_{i, 2} = \max(D_{i - 1, 1}, D_{i - 1, 2}) + B_i\)
• \(D_{i, 3} = \max(D_{i - 1, 2}, D_{i - 1, 3}) + C_i\)

時間計算量は \(O(N)\) です。

実装例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (n); i++)
const ll INF = 1000000000000000010;
template<class T, class U> inline bool chmax(T& a, const U& b) { if (a < b) { a = b; return true; } return false; }

int main() {
	ll n;
	cin >> n;
	vector<ll> a(n), b(n), c(n);
	rep(i, n) cin >> a[i];
	rep(i, n) cin >> b[i];
	rep(i, n) cin >> c[i];
	vector<array<ll, 4>> dp(n + 1);
	rep(i, n + 1) rep(j, 4) dp[i][j] = -INF;
	dp[0][0] = 0;
	rep(i, n) {
		for (int j = 0; j <= 1; j++) chmax(dp[i + 1][1], dp[i][j] + a[i]);
		for (int j = 1; j <= 2; j++) chmax(dp[i + 1][2], dp[i][j] + b[i]);
		for (int j = 2; j <= 3; j++) chmax(dp[i + 1][3], dp[i][j] + c[i]);
	}
	cout << dp[n][3] << '\n';
}