做了一上午血亏
还好最后搞明白一点点；
这是一道dp（最长上升子序列）和贪心题
dp倒是简单 主要是贪心的证明 很难理解 不多做记录了，看了一些题解，感觉讲的都一般，yxc的视频讲解还不错 ， 但是他做的是小数据范围， 可以用二分优化一波；
该文件无法打开 - AcWing yxc视频讲解
#include<iostream> #include<cstring> #include<algorithm> using namespace std ; const int N = 1e5 +100 ; int a[N] , b[N] ; int n ; int q[N] ; int main(){ while(cin >> a[n]) n ++ ; int ans = 0 ; for(int i = n - 1 ; i >= 0 ; i --){ b[i] = a[n-i-1] ; } //第一问就是最长上升子序列问题 for(int i = 0 ; i < n ; i ++){ int l = 0 , r = ans ; while(l < r) { int mid =(r+l+1) >> 1 ; if(q[mid] <= b[i]) l = mid ; else r = mid - 1 ; } ans = max(r+1,ans) ; q[r+1] = b[i] ; } cout << ans << endl; memset(q,0,sizeof(q)) ; //第二题主要考察了贪心思想，尤为难做 //我们遍历每一个数值，找到当前放到结尾大于等于它的最小的序列的后面 //先遍历每个数，再从已经有的序列中找符合上面条件的 //找到以后进行处理：如果当前没有比a[i]更大的数 那他只能自己新开一个序列 然后更新长度也就是子序列的个数（有几个子序列） 然后将我们处理的这个子序列的最后一个结尾数更新成a[i] int len = 0 ; for(int i = 0 ; i < n ;i ++){ int l = 0 ,r = len ; while(l < r){ int mid = (l + r + 1) >> 1 ; if(q[mid] <= a[i]) l = mid ; else r = mid - 1 ; } if(q[r]< a[i]) r ++ ; len = max(len , r) ; q[r] = a[i] ; } cout << len << endl ; }
