luogu1970 NOIP2013花匠

luogu1970 NOIP2013花匠

​​ 题目描述

花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定

把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希

望剩下的花排列得比较别致。

具体而言，栋栋的花的高度可以看成一列整数h1,h2..hn。设当一部分花被移走后，剩下的花的高度依次为g1,g2..gn，则栋栋希望下面两个条件中至少有一个满足：

条件 A：对于所有g(2i)>g(2i-1),g(2i)>g(2i+1)

条件 B：对于所有g(2i)

#include#define N 110000inline int max(int x,int y){ return x>y?x:y;} inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}int n,a[N],s1[N],s2[N];int main(){ freopen("1970.in","r",stdin); //freopen("1970.out","w",stdout); n=read(); for (int i=1;i<=n;++i) a[i]=read(); s1[1]=s2[1]=1; for (int i=2;i<=n;++i){ if (a[i]>a[i-1]){s1[i]=max(s1[i-1],s2[i-1]+1);continue;} if (a[i]==a[i-1]){s1[i]=s1[i-1];s2[i]=s2[i-1];continue;} if (a[i]

今天当作模拟赛又考一遍，写出的做法似乎还不太一样2017.9.28

#include#include#define N 110000using namespace std;inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}int f[N][2],g[N][2],n,h[N];int main(){// freopen("flower.in","r",stdin); n=read(); for (int i=1;i<=n;++i) h[i]=read(); //f[i][0]1~i区间 最后为递增 最长延伸 f[i][1]1~i区间最后为递减 最长延伸 //g[i][0] 定义同上 只是记录的是位置 for (int i=1;i<=n;++i) f[i][0]=f[i][1]=1,g[i][0]=g[i][1]=i; //f[1][0]=f[1][1]=g[1][1]=g[1][0]=1;/* for (int i=2;i<=n;++i){ for(int j=1;jh[g[j][1]]) f[i][0]=f[j][1]+1; if (h[i]h[g[i-1][1]]&&f[i-1][1]+1>f[i][0]) f[i][0]=f[g[i-1][1]][1]+1,g[i][0]=i; if (h[i]>h[g[i-1][0]]&&f[i-1][0]==f[i][0]) g[i][0]=i; if (h[i]f[i][1]) f[i][1]=f[g[i-1][0]][0]+1,g[i][1]=i; } /*for (int i=1;i<=n;++i){ ans=max(f[i][1],max(f[i][0],ans)); } printf("%d",ans);*/ printf("%d",max(f[n][0],f[n][1])); return 0;

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。