自动搬运

查看原文

来自洛谷，原作者为

	juruo_zjc 愿天堂，与你相见

搬运于2025-08-24 21:21:20，当前版本为作者最后更新于2019-01-14 19:58:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

像我这样的蒟蒻往这儿看！

看了其他大佬的题解，蒟蒻我吓得瑟瑟发抖，因为我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;
}