题解 P1970 【花匠】

wuzhoupei

2017-09-22 20:27:05

Solution

作为一道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; } ```