首页 > 代码库 > 最长递增的子序列（模板）

最长递增的子序列（模板）

2024-07-12 23:13:25   221人阅读

一般情况：

[cpp] view plaincopy
  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. }  


 

二分优化

[cpp] view plaincopy
  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. }  


联系
我们