# 14202: 【原4202】植树节

### 题目描述

author: flypig 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4202

# 植树节

## 样例输入

4
1 2 3
4 5 6
7 8 9
1 2 3


## 样例输出

19


## BugenZhao's solution

//
// Created by BugenZhao on 2019/3/18.
//
// 环拆链 动态规划
// 0 矮 1 两边高的中等 2 两边低的中等 3 高

#include <cstdio>
#include <algorithm>

using namespace std;

int value[100005][3];
int ans[100005][4];

int main() {
int n;

scanf("%d", &n);
for (int k = 1; k <= n; ++k) {
scanf("%d%d%d", &value[k][0], &value[k][1], &value[k][2]);
}

int maxAns = -0x7fffffff;

for (int i = 0; i < 4; ++i) {
ans[1][i] = -0x7fffffff;
}
ans[1][0] = value[1][0];
for (int j = 2; j <= n; ++j) {
ans[j][0] = max(ans[j - 1][2], ans[j - 1][3]) + value[j][0];
ans[j][1] = ans[j - 1][3] + value[j][1];
ans[j][2] = ans[j - 1][0] + value[j][1];
ans[j][3] = max(ans[j - 1][0], ans[j - 1][1]) + value[j][2];
}
maxAns = max(maxAns, max(ans[n][2], ans[n][3]));

for (int i = 0; i < 4; ++i) {
ans[1][i] = -0x7fffffff;
}
ans[1][1] = value[1][1];
for (int j = 2; j <= n; ++j) {
ans[j][0] = max(ans[j - 1][2], ans[j - 1][3]) + value[j][0];
ans[j][1] = ans[j - 1][3] + value[j][1];
ans[j][2] = ans[j - 1][0] + value[j][1];
ans[j][3] = max(ans[j - 1][0], ans[j - 1][1]) + value[j][2];
}
maxAns = max(maxAns, ans[n][3]);

for (int i = 0; i < 4; ++i) {
ans[1][i] = -0x7fffffff;
}
ans[1][2] = value[1][1];
for (int j = 2; j <= n; ++j) {
ans[j][0] = max(ans[j - 1][2], ans[j - 1][3]) + value[j][0];
ans[j][1] = ans[j - 1][3] + value[j][1];
ans[j][2] = ans[j - 1][0] + value[j][1];
ans[j][3] = max(ans[j - 1][0], ans[j - 1][1]) + value[j][2];
}
maxAns = max(maxAns, ans[n][0]);

for (int i = 0; i < 4; ++i) {
ans[1][i] = -0x7fffffff;
}
ans[1][3] = value[1][2];
for (int j = 2; j <= n; ++j) {
ans[j][0] = max(ans[j - 1][2], ans[j - 1][3]) + value[j][0];
ans[j][1] = ans[j - 1][3] + value[j][1];
ans[j][2] = ans[j - 1][0] + value[j][1];
ans[j][3] = max(ans[j - 1][0], ans[j - 1][1]) + value[j][2];
}
maxAns = max(maxAns, max(ans[n][0], ans[n][1]));

printf("%d", maxAns);
return 0;
}


## skyzh's solution

#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>

using namespace std;

int dp[100000][3][3];
int _data[100000][3];
int N;

int print_dp() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
cout << j << " " << k << " " << dp[i][j][k] << endl;
}
cout << endl;
}
cout << endl;
}
}

int dp_first(int k1) {
memset(dp, 0, sizeof(dp));
for (int j = 0; j < 3; j++)
for (int k = 0; k < 3; k++)
if (k != k1) dp[0][j][k] = INT_MIN;
else dp[0][j][k] = _data[0][k];
for (int i = 1; i < N; i++) {
for (int j = 0; j < 3; j++) {
for (int x2 = 0; x2 < 3; x2++) {
int _m = INT_MIN;
for (int x1 = 0; x1 < 3; x1++) {
if (x1 < x2 && x2 > j || x1 > x2 && x2 < j) {
_m = max(dp[i - 1][x1][x2] + _data[i][j], _m);
}
}
dp[i][x2][j] = _m;
}
}
}
int result = 0;
for (int x1 = 0; x1 < 3; x1++) {
if (k1 == 0) {
for (int x2 = 1; x2 < 3; x2++) {
result = max(result, dp[N - 1][x1][x2]);
}
}
if (k1 == 2) {
for (int x2 = 0; x2 < 2; x2++) {
result = max(result, dp[N - 1][x1][x2]);
}
}
}
return result;
}

int dp_second(int k2) {
memset(dp, 0, sizeof(dp));
for (int j = 0; j < 3; j++)
for (int k = 0; k < 3; k++)
if (k != k2 || j != 1) dp[1][j][k] = INT_MIN;
else dp[1][j][k] = _data[1][k] + _data[0][j];
for (int i = 2; i < N; i++) {
for (int j = 0; j < 3; j++) {
for (int x2 = 0; x2 < 3; x2++) {
int _m = INT_MIN;
for (int x1 = 0; x1 < 3; x1++) {
if (x1 < x2 && x2 > j || x1 > x2 && x2 < j) {
_m = max(dp[i - 1][x1][x2] + _data[i][j], _m);
}
}
dp[i][x2][j] = _m;
}
}
}
int result = 0;
for (int x1 = 0; x1 < 3; x1++) {
if (k2 == 0) {
result = max(result, dp[N - 1][x1][0]);
}
if (k2 == 2) {
result = max(result, dp[N - 1][x1][2]);
}
}
return result;
}

int main() {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d%d%d", &_data[i][0], &_data[i][1], &_data[i][2]);
}
int dp0 = dp_first(0);
int dp1 = dp_second(0);
int dp2 = dp_second(2);
int dp3 = dp_first(2);
printf("%d\n", max(max(max(dp0, dp1), dp2), dp3));
return 0;
}