链接:https://www.nowcoder.com/acm/contest/116/C
来源:牛客网 题目描述
杨老师认为他的学习能力曲线是一个拱形。勤奋的他根据时间的先后顺序罗列了一个学习清单,共有n个知识点。但是清单中的知识并不是一定要学习的,可以在不改变先后顺序的情况下有选择的进行学习,而每一个知识点都对应一个难度值。杨老师希望,后学习的知识点的难度一定不低于前一个知识点的难度(i<j时ai<=aj),而可能存在一个临界点,在临界点以后,他希望后学习的知识点的难度一定不高于前一个知识点的难度(i<j时ai>=aj)。杨老师想尽可能多的学习知识。请问:杨老师最多可以学习多少知识?
输入描述:
第一行:一个整数n(0<n<500000)接下来一行:n个整数,第i个整数ai(0<=ai<500000)表示第i道题目的难度。
输出描述:
一行一个整数,表示杨老师最多可以学习多少个知识。
示例1
输入
5
1 4 2 5 1
输出
4

【分析】:类似《合唱队形》,双向LIS,注意不严格单调(即可以相等)用upper_bound!

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int b[N],le[N],ri[N],n,ans=0x7fffffff;
void lis1(){
int f[N],len=1;
f[1]=b[1];
le[1]=1;
for(int i=2;i<=n;i++){
if(f[len]<=b[i]) f[++len]=b[i];
else f[upper_bound(f+1,f+len+1,b[i])-f]=b[i];
le[i]=len;
}
}
void lis2(){
int f[N], len=1;
f[1]=b[n];
for(int i=n-1;i>=1;i--){
if(f[len]<=b[i]) f[++len]=b[i];
else f[upper_bound(f+1,f+len+1,b[i])-f]=b[i];
ri[i]=len;
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>b[i];
lis1();lis2();
for(int i=1;i<=n;i++)
ans=min(ans,n-le[i]-ri[i+1]);
cout<<n-ans;
}
05-08 08:21