hdu 4604 Deque

http://acm.hdu.edu.cn/showproblem.php?pid=4604

想了半天，发现是LIS，O（nlgn）飘过。

具体思路：预处理好以i为开头的（下面我用逆序输入，所以是以i为结尾的）LIS和LDS。

　　　　　再枚举每个点找最优即可（注意不严格递增、减）。

  1 #include<map>
  2 #include<set>
  3 #include<list>
  4 #include<cmath>
  5 #include<ctime>
  6 #include<queue>
  7 #include<stack>
  8 #include<cctype>
  9 #include<cstdio>
 10 #include<string>
 11 #include<vector>
 12 #include<cstdlib>
 13 #include<cstring>
 14 #include<iostream>
 15 #include<algorithm>
 16 #define MAXN 100005
 17 using namespace std;
 18 int num[MAXN], n;
 19 int dpI[MAXN], lenI[MAXN];    //I:increasing
 20 int dpD[MAXN], lenD[MAXN];    //D:decreasing
 21 int cntI[MAXN], cntD[MAXN];    
 22 //cnt[i]记录以i结尾的子序列中num[i]的重复个数。
 23 
 24 int searchI(int x)
 25 {
 26     //printf("done
");
 27     int l=1, r=n, m;
 28     while(l <= r)
 29     {
 30         m = (l+r)/2;
 31         if(x >= lenI[m])
 32             l = m+1;
 33         else
 34             r= m-1;
 35     }
 36     return l-1;
 37 }
 38 
 39 int searchD(int x)
 40 {
 41     int l=1, r=n, m;
 42     while(l <= r)
 43     {
 44         m = (l+r)/2;
 45         if(x <= lenD[m])
 46             l = m+1;
 47         else
 48             r= m-1;
 49     }
 50     return l-1;
 51 }
 52 
 53 void print(int *x)
 54 {
 55     for(int i=1; i<=n; i++)
 56         printf("%d ", x[i]);
 57     printf("
");
 58 }
 59 
 60 int main()
 61 {    
 62     //hdu 1005
 63     int t;
 64     cin >> t;
 65     while(t--){
 66         cin >> n;
 67         for(int i=n; i>=1; i--)
 68             scanf("%d", &num[i]);
 69         //为了方便处理，逆序输入。
 70         memset(lenI, 0x3f, sizeof(lenI));
 71         for(int i=1; i<=n; i++){
 72             lenD[i] = -0x3f3f3f3f;
 73             cntI[i] = cntD[i] = 1;
 74         }
 75         
 76         for(int i=1; i<=n; i++){
 77             int k = searchI(num[i]);
 78             dpI[i] = k + 1;
 79             if(lenI[k] == num[i])
 80                 cntI[k+1] = cntI[k]+1;
 81             lenI[dpI[i]] = min(lenI[dpI[i]], num[i]);    
 82         }
 83         
 84         for(int i=1; i<=n; i++){
 85             int k = searchD(num[i]);
 86             dpD[i] = k + 1;
 87             if(lenD[k] == num[i])
 88                 cntD[k+1] = cntD[k]+1;
 89             lenD[dpD[i]] = max(lenD[dpD[i]], num[i]);
 90         }
 91         //print(dpI);
 92         //print(dpD);
 93         
 94         int ans = 0;
 95         for(int i=1; i<=n; i++)
 96             ans = max(ans, dpI[i]+dpD[i]-min(cntI[i], cntD[i]));
 97         printf("%d
", ans);
 98         
 99     }
100 
101     return 0;
102 }

View Code

可以做一下类似题：EOJ 1237 　　O（n^2）水过

http://www.acm.cs.ecnu.edu.cn/problem.php?problemid=1237