题解 P1970 【花匠】
wuzhoupei
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
```cpp
#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;
}
```