大家似乎都是贪心或连贪带规。蒟蒻的思维很简单
对于一朵花,如果选它,那么只有两种状态:比上一个矮或者比上一个高
$dp_{i,0}$ 比上一个矮,$dp_{i,1}$ 比上一个高
$dp_{i,0}=\operatorname{max}(dp_{j,1})$,$j\in [1,i-1]$,$h_j>h_i$
$dp_{i,1}$ 同理
但复杂度是 $O(n^2)$,于是有了线段树优化
一个掌管 $l$ 到 $r$ 的区间的线段树结点,表示高度为 $l$ 到 $r$ 的花的DP值的最大值,复杂度$O(n\log n)$
#include<iostream>
#define L(x) (x<<1)
#define R(x) ((x<<1)|1)
#define MX 1000006
using namespace std;
int arr[100005];
int dp[100005][2];
int seg0[1000006<<2],seg1[1000006<<2];
int search(int*seg,int sl,int sr,int p=1,int l=0,int r=MX)
{
if(l>sr||r<sl)return -0x3f3f3f3f;
if(l>=sl&&r<=sr)return seg[p];
int mid=(l+r)>>1;
return max(search(seg,sl,sr,L(p),l,mid),search(seg,sl,sr,R(p),mid+1,r));
}
void add(int*seg,int aim,int v,int p=1,int l=0,int r=MX)
{
if(l==r)
{
seg[p]=max(seg[p],v);
return;
}
int mid=(l+r)>>1;
if(aim<=mid)add(seg,aim,v,L(p),l,mid);
else add(seg,aim,v,R(p),mid+1,r);
seg[p]=max(seg[L(p)],seg[R(p)]);
}
int main()
{
freopen("flower.in","r",stdin);
freopen("flower.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;++i)cin>>arr[i];
for(int i=1;i<=n;++i)
{
dp[i][0]=search(seg1,arr[i]+1,MX)+1;
dp[i][1]=search(seg0,0,arr[i]-1)+1;
add(seg0,arr[i],dp[i][0]);
add(seg1,arr[i],dp[i][1]);
}
cout<<max(dp[n][0],dp[n][1]);
}