$RT$，我这个蒟蒻又不要脸地 @ 巨佬们了

（帮帮我这个蒟蒻吧，感觉思路差不多，但只有$10$分啊）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100010
#define ZZ register long long
using namespace std;

long long n, dp[MAXN][3][3];
long long a[MAXN][4], ans;

inline long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int main() {
    n = read();
    for (ZZ i = 1; i <= n; i++) {
        for (ZZ j = 1; j <= 3; j++)
            a[i][j] = read();
    }
    dp[2][1][0] = a[2][2] + a[1][1]; dp[2][2][0] = a[2][3] + a[1][1];
    for (ZZ i = 3; i <= n; i++) {
        for (ZZ j = 0; j <= 2; j++) {
            for (ZZ k = 0; k <= 2; k++) {
                if (j == k) dp[i][j][k] = 0;
                else if (j < k) {
                    for (ZZ m = k - 1; m >= 0; m--) dp[i][k][m] = max(dp[i - 1][j][k] + a[i][m + 1], dp[i][k][m]);
                } else if (j > k) {
                    for (ZZ m = k + 1; m <= 2; m++) dp[i][k][m] = max(dp[i - 1][j][k] + a[i][m + 1], dp[i][k][m]);
                }
            }
        }
    }
    ans = max(dp[n][1][0], max(dp[n][2][1], dp[n][2][0]));
    memset(dp, 0, sizeof(dp));
    dp[2][2][1] = a[2][3] + a[1][2]; dp[2][0][1] = a[2][1] + a[1][2];
    for (ZZ i = 3; i <= n; i++) {
        for (ZZ j = 0; j <= 2; j++) {
            for (ZZ k = 0; k <= 2; k++) {
                if (j == k) dp[i][j][k] = 0;
                else if (j < k) {
                    for (ZZ m = k - 1; m >= 0; m--) dp[i][k][m] = max(dp[i - 1][j][k] + a[i][m + 1], dp[i][k][m]);
                } else if (j > k) {
                    for (ZZ m = k + 1; m <= 2; m++) dp[i][k][m] = max(dp[i - 1][j][k] + a[i][m + 1], dp[i][k][m]);
                }
            }
        }
    }
    ans = max(ans, max(dp[n][0][1], max(dp[n][0][2], max(dp[n][2][0], dp[n][2][1]))));
    memset(dp, 0, sizeof(dp));
    dp[2][0][2] = a[2][1] + a[1][3]; dp[2][1][2] = a[2][2] + a[1][3];
    for (ZZ i = 3; i <= n; i++) {
        for (ZZ j = 0; j <= 2; j++) {
            for (ZZ k = 0; k <= 2; k++) {
                if (j == k) dp[i][j][k] = 0;
                else if (j < k) {
                    for (ZZ m = k - 1; m >= 0; m--) dp[i][k][m] = max(dp[i - 1][j][k] + a[i][m + 1], dp[i][k][m]);
                } else if (j > k) {
                    for (ZZ m = k + 1; m <= 2; m++) dp[i][k][m] = max(dp[i - 1][j][k] + a[i][m + 1], dp[i][k][m]);
                }
            }
        }
    }
    ans = max(ans, max(dp[n][0][2], max(dp[n][0][1], dp[n][1][2])));
    printf("%d\n", ans);
    return 0;
}

其中 dp[n][0/1/2][0/1/2]表示在第n个位置放的树的状态为(0/1/2), 第$n - 1$个位置放的树的状态为(0/1/2)的最大价值（其中0状态表示）

@⚡小林子⚡

@陆麟瑞

@zhangyuhan

@Catalan1906

@LightningUZ

@Rainy7

@暴力出奇迹

@LHQing

@WYXkk