自动搬运

查看原文

来自洛谷，原作者为

	wuzhoupei 大学狗QQ1208247864

搬运于2025-08-24 21:32:27，当前版本为作者最后更新于2017-09-22 20:27:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

作为一道NOIP真题，这道题个人感觉比较水，稍稍用到了DP的思想；

我们仔细分析，发现两个条件可以总结为：求一个最长序列，使得该序列的任意三个相邻元素，中间的元素是三个中最大的，或者最小的；

对此，我们可以联想到最长不下降子序列，这道题我是由此想到正解的；

比如元素d[i]和d[j]，假设d[i]>d[j]且j>i，那么我们会让long_[j]=max(long_[j],long_[i]+1); 那么我们可以类比一下，最长不下降子序列是在当前节点前面找一个符合条件的，那么我们这道题也可以作为一道最长不下降子序列来做，只是当前节点寻找前驱的范围是前一个节点，而且我们还要用同样的方法求一个最长不上升子序列，最后取max，那么这道题就完了；

细节处理见代码：

(代码中的最高最低全部是以当前节点为中心时的相对值)

我的博客： http://blog.csdn.net/pretend\_fal

#include<iostream>
#include<cstdio>
#define II int
#define R register
#define I 123456
using namespace std;


II a[I],d_1[I],d_2[I];

II n;


int main()
{
//  freopen("FlowerNOIP2013.in","r",stdin);
//  freopen("FlowerNOIP2013.out","w",stdout);
    scanf("%d",&n);
    R II x;
    for(R II i=1;i<=n;i++) scanf("%d",&x), a[i]=x;
    d_1[1]=d_2[1]=1;
    //d_1[]代表的是当前元素是以当前元素为中心的三个相邻的元素中最大的；
    //同理，d_2[]代表的是当前元素是以当前元素为中心的三个相邻的元素中最小的；
    //但是当前元素不一定选，可能是继承上一个元素的信息；
    for(R II i=2;i<=n;i++)
    {
        if(a[i]>a[i-1]) d_1[i]=max(d_1[i-1],d_2[i-1]+1), d_2[i]=d_2[i-1];
        //如果当前元素大于这个前一个元素；
        //那么当前元素若果选，则是前一个元素作为最低点时的长度+1；
        //如果不选，就继承前一个元素作为最高点，等价于当前元素作为最高点；
        //当前元素作为最低点就只能继承前一个点作为最低点；
            else{
                if(a[i]<a[i-1]) d_1[i]=d_1[i-1], d_2[i]=max(d_1[i-1]+1,d_2[i-1]);
                //如果当前元素小于前一个元素，则道理同上，只是反过来；
                    else d_1[i]=d_1[i-1],   d_2[i]=d_2[i-1];
                    //如果当前元素等于前一个元素，那么这个元素直接继承前一个元素的所有信息；
                    //因为这两个点是完全等价的；
            }
    }
    R II ans=max(d_1[n],d_2[n]);
    //我们在最后时取两种状态的最大值作为答案；
    cout<<ans<<endl;
    return 0;
}