day2 花匠

day2的第二题其实也蛮友好的呢，刚看还被吓了下，仔细一想，诶，这不是找找拐点不就完了么？时间复杂度仅为O(n)。注意，一段连续且相等的数字，只留一个，其他删掉，下面贴出代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,h[100005],ans=1,ans2;
int main()
{
    freopen("flower.in","r",stdin);
    freopen("flower.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&h[i]);
        if(h[i]==h[i-1])
        i--,n--;
    }
    for (int i=2;i<=n-1;i++)
    {
        if(h[i]>h[i-1]&&h[i]>h[i+1]||h[i]<h[i-1]&&h[i]<h[i+1])
        ans++;
    }
    cout<<ans+1;
    return 0;
}

当然，利用动态规划+线段树或树状数组也是可以完成的，时间复杂度会高一些，为O(nlogn)，下面同样给出代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 100010
#define lowbit(x)(((~(x))+1)&x)
#define MAXH 1000010
#define For(i,x) for (int i=x;i;i-=lowbit(i))
#define rep(i,x) for (int i=x;i<=maxh;i+=lowbit(i))
int t0[MAXH],t1[MAXH];
int h[MAXN],n,maxh=0;
int f[MAXN][2],ans=0;
void Add0(int x,int y) {
    rep(i,x) t0[i]=max(t0[i],y);
}
void Add1(int x,int y) {
    rep(i,x) t1[i]=max(t1[i],y);
}
int Max0(int x) {
    int rec=0;
    For(i,x) rec=max(rec,t0[i]);
    return rec;
}
int Max1(int x) {
    int rec=0;
    For(i,x) rec=max(rec,t1[i]);
    return rec;
}
int main() {
    scanf("%d",&n);
    for (int i=0;i++<n;) {
        scanf("%d",&h[i]);
        maxh=max(maxh,++h[i]);
        f[i][0]=f[i][1]=1;
    }
    maxh++;
    memset(t0,0,sizeof(t0)),memset(t1,0,sizeof(t1));
    for (int i=0;i++<n;) {
        f[i][0]=max(Max0(h[i]-1)+1,f[i][0]);
        f[i][1]=max(Max1(maxh-h[i]-1)+1,f[i][1]);
        Add0(h[i],f[i][1]),Add1(maxh-h[i],f[i][0]);
        ans=max(ans,max(f[i][0],f[i][1]));
    }
    printf("%d\n",ans);
    return 0;

代码摘自网上，，，

清清正正射命丸文是也~