模板最长递增子序列

【模板】最长递增子序列

一般情况：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 using namespace std;
 5 
 6 int a[1005],dp[1005],n;
 7 
 8 int LIS()
 9 {
10     int i,j,ans,m;
11     dp[1] = 1;
12     ans = 1;
13     for(i = 2;i<=n;i++)
14     {
15         m = 0;
16         for(j = 1;j<i;j++)
17         {
18             if(dp[j]>m && a[j]<a[i])
19             m = dp[j];
20         }
21         dp[i] = m+1;
22         if(dp[i]>ans)
23         ans = dp[i];
24     }
25     return ans;
26 }

二分优化：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int a[40005],dp[40005],n;
 7 
 8 int bin(int size,int k)
 9 {
10     int l = 1,r = size;
11     while(l<=r)
12     {
13         int mid = (l+r)/2;
14         if(k>dp[mid])
15             l = mid+1;
16         else
17             r = mid-1;
18     }
19     return l;
20 }
21 
22 int LIS()
23 {
24     int i,j,ans=1;
25     dp[1] = a[1];
26     for(i = 2; i<=n; i++)
27     {
28         if(a[i]<=dp[1])
29             j = 1;
30         else if(a[i]>dp[ans])
31             j = ++ans;
32         else
33             j = bin(ans,a[i]);
34         dp[j] = a[i];
35     }
36     return ans;
37 }

模板 最长递增子序列

模板最长递增子序列