洛谷：P1020导弹拦截（dp，最长上升加强版，典例，nlogn）

题目：

值的思考的问题：该题目还要进行最少下降串的查找，如何查找。

分析：看打蜡的：

代码：

#include
using namespace std;
int m;
int A[100005];
int D1[100005];
int D2[100005];
int main()
{string s;getline(cin,s);stringstream ss(s);int c;int c2=0;while(ss>>c){A[c2]=c;c2++;}m=c2;//for(int i=0;i//cout<D1[0]=A[0];D2[0]=A[0];int len1 = 0, len2 = 0;for (int i=1; i<m; i++) { //从a[2]开始枚举每个数(a[1]已经加进去了)if (D1[len1]>= A[i]) D1[++len1] = A[i]; //如果满足要求(不上升)就加入d1else { //否则用a[i]替换d1中的一个数int p1 = upper_bound(D1, D1 + len1, A[i], greater<int>())-D1;D1[p1] = A[i]; }if (D2[len2] < A[i]) D2[++len2] = A[i]; //同上else {int p2 = lower_bound(D2, D2 + len2,A[i]) - D2;D2[p2] = A[i];}}cout<<len1+1<<endl<<len2+1;
}