LuoguP1133 教主的花园

经典线性dp。

Sol.

典型的线性dp，首先考虑二维：

记 \(f_{i,j}\) 表示当前为第 \(i\) 位，放第 \(j\) 种树的最大值。

然后我们发现我们没办法很好地表示树之间的高低关系，于是我们再加一维：

记 \(f_{i,j,0/1}\) 表示当前为第 \(i\) 位，放第 \(j\) 种树，当前树比上一位树 \(0(高)/1(低)\) 的最大值。

我们可以很顺利地推出转移方程：

\[ f_{i,j,0} = \max\limits_{k<j}\{f_{i-1,k,1}\}\\ f_{i,j,0} = \max\limits_{k>j}\{f_{i-1,k,0}\} \]

如果这题只是一条线，那么这题到此为止就已经完成了。但是这道题是在环上，所以我们还要考虑如何处理头和尾。在记一维 \(s\) 表示第一位是那种树。即变成：

记 \(f_{i,j,s,0/1}\) 表示当前为第 \(i\) 位，放第 \(j\) 种树，第一位放 \(s\) 种树，当前树比上一位树 \(0(高)/1(低)\) 的最大值。

\[ \text{if}\ \ 2\leq i<n \begin{cases} f_{i,j,s,0} = \max\limits_{k<j}\{f_{i-1,k,s,1}\}\\ f_{i,j,s,1} = \max\limits_{k>j}\{f_{i-1,k,s,0}\}\\ \end{cases}\\ \text{if}\ \ i=n \begin{cases} f_{n,j,s,0} = \max\limits_{k<j}\{f_{n-1,k,s,1}\}& \text{if}\ j>s\\ f_{n,j,s,0} = \max\limits_{k>j}\{f_{n-1,k,s,0}\}& \text{if}\ j<s\\ \end{cases} \]

Code

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 7;

int a[MAXN][4], f[MAXN][4][4][2]; //f(i,j,s,0/1)

int n, ans = -1;

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]);
    }
    for(int j = 1; j <= 3; j++)
	{
		f[1][j][j][0] = f[1][j][j][1] = a[1][j];
	}
    for(int i = 2; i < n; i++)
        for(int j = 1; j <= 3; j++)
            for(int s = 1; s <= 3; s++)
            {
                for(int k = j + 1; k <= 3; k++) f[i][j][s][1] = max(f[i][j][s][1], f[i - 1][k][s][0] + a[i][j]);
                for(int k = j - 1; k >= 1; k--) f[i][j][s][0] = max(f[i][j][s][0], f[i - 1][k][s][1] + a[i][j]);
            }
    for(int j = 1; j <= 3; j++)
        for(int s = 1; s <= 3; s++)
        {
            if(s < j)
                for(int k = j - 1; k >= 1; k--) f[n][j][s][0] = max(f[n][j][s][0], f[n - 1][k][s][1] + a[n][j]);
            if(s > j)
                for(int k = j + 1; k <= 3; k++) f[n][j][s][1] = max(f[n][j][s][1], f[n - 1][k][s][0] + a[n][j]);
            ans = max(ans, max(f[n][j][s][0], f[n][j][s][1]));
        }
    printf("%d\n", ans);
    return 0;
}