题解 P1133 【教主的花园】

freesaber · 2020-03-16 17:23:42 · 题解

这道题我主要想说一种解决环的方法。 我们可以直接在第 n 个位置后面再加上一个位置，这个位置的各种属性与第一个位置相同。通俗的来说就是 把第一个位置再复制一份到第n+1个位置。然后在动态规划时多规划一个位置（即：第n+1个位置），这样就可以解决首尾相邻的问题了。

#include <cstdio>
#include <algorithm>
using namespace std;
const int Max = 100000 + 5;
int a[Max][5], f[Max][5][4], n;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d", &a[i][1], &a[i][2], &a[i][3]);
    }
    a[n + 1][1] = a[1][1]; //复制第一个位置
    a[n + 1][2] = a[1][2];
    a[n + 1][3] = a[1][3];
    n++; //多规划一个位置
    for (int i = 2; i <= n; i++) {
        f[i][1][1] = max(f[i - 1][2][2], f[i - 1][3][2]) + a[i][1];
        f[i][2][1] = f[i - 1][3][2] + a[i][2];
        f[i][2][2] = f[i - 1][1][1] + a[i][2];
        f[i][3][2] = max(f[i - 1][2][1], f[i - 1][1][1]) + a[i][3];
    }
    int ans = -1;
    for (int i = 1; i <= 3; i++) //枚举第n+1个位置
        for (int j = 1; j <= 2; j++)
            ans = max(ans, f[n][i][j]);
    printf("%d\n", ans);
    return 0;
}