https://www.luogu.org/problemnew/show/P1020
终于搞明白了。根据某定理，最少需要的防御系统的数量就是最长上升子序列的数量。
呵呵手写二分果然功能很多，想清楚自己要找的是什么就可以了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n;
int a[100005];
int dp[50005];
int f1(int *dp,int a){
int l=1,r=n;
while(1){
int m=(l+r)>>1;
if(m==l){
if(dp[l]<a)
return l;
else
return r;
}
if(dp[m]<a){
r=m;
}
else{
l=m+1;
}
}
return -1;
}
int f2(int *dp,int a){
int l=1,r=n;
while(1){
int m=(l+r)>>1;
if(m==l){
if(dp[l]>=a)
return l;
else
return r;
}
if(dp[m]>=a){
r=m;
}
else{
l=m+1;
}
}
return -1;
}
int main(){
n=0;
int t;
while(~scanf("%d",&t)){
n++;
a[n]=t;
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
int id=f1(dp,a[i]);
//cout<<"id="<<id<<endl;
dp[id]=a[i];
/*for(int k=1;k<=n;k++){
printf("dp[%d]=%d\n",k,dp[k]);
}*/
}
int ans=n;
for(int i=1;i<=n;i++){
if(dp[i]==0){
ans=i-1;
break;
}
}
printf("%d\n",ans);
memset(dp,INF,sizeof(dp));
for(int i=1;i<=n;i++){
int id=f2(dp,a[i]);
//cout<<"id="<<id<<endl;
dp[id]=a[i];
/*for(int k=1;k<=n;k++){
printf("dp[%d]=%d\n",k,dp[k]);
}*/
}
ans=n;
for(int i=1;i<=n;i++){
if(dp[i]==INF){
ans=i-1;
break;
}
}
printf("%d\n",ans);
}