luogu1970 NOIP2013花匠

​​http://www.elijahqi.win/archives/499​​​
题目描述

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

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

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

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

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

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

#include<cstdio>
#define N 110000
inline 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]<a[i-1])s2[i]=max(s2[i-1],s1[i-1]+1);
}
printf("%d",max(s1[n],s2[n]));
return 0;
}

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

#include<cstdio>
#include<algorithm>
#define N 110000
using 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;j<i;++j){
if (h[i]>h[g[j][1]]) f[i][0]=f[j][1]+1;
if (h[i]<h[g[j][0]]) f[i][1]=f[j][0]+1;
}
}int ans=0;*/
for(int i=2;i<=n;++i){
f[i][0]=f[i-1][0],g[i][0]=g[i-1][0];
f[i][1]=f[i-1][1],g[i][1]=g[i-1][1];
if (h[i]<h[g[i-1][1]]&&f[i-1][1]==f[i][1]) g[i][1]=i;
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]<h[g[i-1][0]]&&f[i-1][0]+1>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;