1010. 拦截导弹（dp模版二 最长上升子序列

题源
求导弹的可拦截个数是最长下降子序列
求导弹的发射个数是最长上升子序列（证明是一个定理

#include<bits/stdc++.h>usingnamespacestd;constintN=1009;intarr[N],dpDe[N],dpIn[N],tot=0;intansDe=0,ansIn=0;intmain(){intansDe=0,ansIn=0;while(cin>>arr[++tot]){}//cout<<tot<<endl;for(inti=1;i<tot;i++){dpDe[i]=1;dpIn[i]=1;for(intj=1;j<i;j++){if(arr[j]<arr[i]){dpIn[i]=max(dpIn[j]+1,dpIn[i]);// cout<<arr[j]<<" "<<arr[i]<<" "<<dpIn[j]<<" "<<dpIn[i]<<endl;}if(arr[j]>=arr[i]){dpDe[i]=max(dpDe[j]+1,dpDe[i]);}}ansDe=max(dpDe[i],ansDe);ansIn=max(dpIn[i],ansIn);}cout<<ansDe<<"\n"<<ansIn;return0;}