T1 P1133 教主的花园

传送门：洛谷P1133

这是一道DP的题，定义状态 \(dp[i][j][k]\) 表示前 \(i\) 棵树所能达到的最大价值，且第 \(i\) 棵树为第 \(j\) 种树，\(j = 0\) 高度是 \(10\)，\(j = 1\) 高度是 \(20\)， \(j = 2\) 高度为 \(30\)，如果 \(k = 0\) 它的高度小于相邻两颗， \(k = 1\) 则相反；

状态转移方程：

\(dp[i][0][0] = max(dp[i - 1][1][1], dp[i - 1][2][1]) + w[i];\)
\(dp[i][1][0] = dp[i - 1][2][1] + w[i];\)
\(dp[i][1][1] = dp[i - 1][0][0] + w[i];\)
\(dp[i][2][1] = max(dp[i - 1][1][0], dp[i - 1][0][0]) + w[i];\)

坑点：

因为这是一个环，我们还要考虑 \(1, n\) 的高度关系，那么我们每次枚举一下 \(1\) 的高度就行了，然后取 \(max\);

贴代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;
int a[maxn][3], dp[maxn][3][2], n;

void read() {
    scanf("%d", &n);
    int ans = 0;
    for (int i = 1; i <= n; ++ i)
        scanf("%d%d%d", &a[i][0], &a[i][1], &a[i][2]);
    for (int j = 0; j < 3; ++ j) {
        for (int i = 0; i < 3; ++ i)
            for (int k = 0; k < 2; ++ k)
                dp[1][i][k] = 0;
        dp[1][j][0] = dp[1][j][1] = a[1][j];
        for (int i = 2; i <= n; ++ i) {
            dp[i][0][0] = max(dp[i - 1][1][1], dp[i - 1][2][1]) + a[i][0];
            dp[i][1][0] = dp[i - 1][2][1] + a[i][1];
            dp[i][1][1] = dp[i - 1][0][0] + a[i][1];
            dp[i][2][1] = max(dp[i - 1][0][0], dp[i - 1][1][0]) + a[i][2];
        }
        for (int i = 0; i < j; ++ i)
            ans = max(ans, dp[n][i][0]);
        for (int i = 2; i > j; -- i)
            ans = max(ans, dp[n][i][1]);
    }
    printf("%d\n", ans);
}

int main() {
    read();
    return 0;
}