题解 P1133 【教主的花园】
像我这样的蒟蒻往这儿看！
看了其他大佬的题解，蒟蒻我吓得瑟瑟发抖，因为我kan bu dong，于是，做完后我决定写一篇平民化的题解
我为什么会做这道题？
答案就是，这道题是DP题
我为什么对DP情有独钟？
因为NOIP考试时在第三题上爆炸了呗！
看了其他大佬的题解，蒟蒻我吓得瑟瑟发抖，因为我kan bu dong，于是，做完后我决定写一篇平民化的题解
好了，不多说了，直切猪蹄（主题）
定义dp[i][j][k]为在第i个位置，种第j种树（明显j有三种，这里定义j=0为高度为10的树，j=1为高度为20的树，j=2为高度为30的树）比左右的树高/低，（k=0表示比左右的树低，k=1则表示比左右的高）
什么叫比左右都高？大家都知道吧？什么？你不知道？
上图中，中间那根比左右都高，反过来就是左右的比它都低。
然后决策吧！
对于每个位置，它可以种三种树。
如果是种高度为10的树
就只有dp[i][0][0]的情况，为什么？因为它是最矮的树，没有树比它更矮，所以只可能比左右都矮。那么dp[i][0][0]怎么由上一个状态转移过来呢？
dp[i][0][0]=max(dp[i-1][1][1],dp[i-1][2][1])+a[i][0];
考虑它的上一个位置，dp[i-1]，它可以种高度为20的树或高度为30的树，绝对不可能种高度为10的树，因为状态中，第i位置的树是比左右都低的，因为k=0。想想看，第i个位置比左右低，是不是意味着左右位置都比第i位置高？于是就与dp[i-1][1][1]和dp[i-1][2][1]作决策，取最大值，加上本位置的观赏价值。
如果是种高度为20的树呢？
它有dp[i][1][0]和dp[i][1][1]两种情况，它既可以比左右都高，也可以比左右都低。状态转移如下：
dp[i][1][1]=dp[i-1][0][0]+a[i][1];
dp[i][1][0]=dp[i-1][2][1]+a[i][1];
考虑它的上一个位置，dp[i-1]，如果第i位置比左右都高的话，它的前一个位置只能是高度为10的，为什么？因为第i位置的高度为20，比它低的只有高度为10的，所以dp[i][1][1]=dp[i-1][0][0]+a[i][1];如果i位置比左右都低呢？那么i-1位置只能为30，原因同上，所以dp[i][1][0]=dp[i-1][2][1]+a[i][1];
如果是种高度为30的树呢？
这其实和高度为10一样，只有比别的高dp[i][2][1]的情况。这里不做赘述。
dp[i][2][1]=max(dp[i-1][1][0],dp[i-1][0][0])+a[i][2];
原理同高度为10的一样。
还有一些程序小细节，就具体看代码吧！
#include<bits/stdc++.h>
using namespace std;
int dp[100010][3][2],n,a[100010][3],ans;
int main()
{
cin>>n;
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;//初始化，全部赋值为0
dp[1][j][0]=dp[1][j][1]=a[1][j];//初始值为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][1][0],dp[i-1][0][0])+a[i][2];
}
for(int i=0;i<j;i++)ans=max(ans,dp[n][i][0]);//分类迭代ans，<=j的高度肯定是比它矮的，所以为dp[n][i][0]
for(int i=2;i>j;i--)ans=max(ans,dp[n][i][1]);//与上述类似，>j的肯定是比它高的，所以为dp[n][i][1]
}
printf("%d",ans);//输出结果
return 0;
}