POJ 2533 Longest Ordered Subsequence （LIS DP）

最长公共自序列LIS

三种模板，但是邝斌写的好像这题过不了

N*N

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int N = 41000;
 6 int a[1010],dp[1010],n;
 7 int Lis(){
 8    dp[1]=1;
 9    int ans=1;
10    int temp=0;
11    for(int i=2;i<=n;i++){
12       temp=0;
13       for(int j=1;j<i;j++){
14         if(dp[j]>temp&&a[i]>a[j]){
15             temp=dp[j];
16         }
17       }
18       dp[i]=temp+1;
19       if(dp[i]>ans){
20         ans=dp[i];
21       }
22    }
23    return ans;
24 }
25 int main(){
26     while(~scanf("%d",&n)){
27         for(int i=1;i<=n;i++){
28             scanf("%d",&a[i]);
29         }
30         printf("%d
",Lis());
31     }
32      return 0;
33 }

View Code

N*logn

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 using namespace std;
 5 
 6 int a[1005],dp[1005],c[1005],n;
 7 
 8 int bin(int sizee,int k)
 9 {
10     int l = 1,r = sizee;
11     while(l<=r)
12     {
13         int mid = (l+r)/2;
14         if(k>c[mid] && k<=c[mid+1])
15             return mid+1;
16         else if(k<c[mid])
17             r = mid-1;
18         else
19             l = mid+1;
20     }
21 }
22 
23 int LIS()
24 {
25     int i,j,ans=1;
26     c[1] = a[1];
27     dp[1] = 1;
28     for(i = 2; i<=n; i++)
29     {
30         if(a[i]<=c[1])
31             j = 1;
32         else if(a[i]>c[ans])
33             j = ++ans;
34         else
35             j = bin(ans,a[i]);
36         c[j] = a[i];
37         dp[i] = j;
38     }
39     return ans;
40 }
41 
42 int main()
43 {
44     int i;
45     while(~scanf("%d",&n))
46     {
47         for(i = 1; i<=n; i++)
48             scanf("%d",&a[i]);
49         printf("%d
",LIS());
50 
51     }
52     return 0;
53 }

View Code

没有AC

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #define clc(a,b) memset(a,b,sizeof(a))
 6 #define LL long long
 7 #include<cmath>
 8 const int inf=0x3f3f3f3f;
 9 using namespace std;
10 const int MAXN=500010;
11 int a[MAXN],b[MAXN];
12 int Serch(int num,int low,int high) {
13     int mid;
14     while(low<=high) {
15         mid=(low+high)/2;
16         if(num>=b[mid])
17             low=mid+1;
18         else high=mid-1;
19     }
20     return low;
21 }
22 int Dp(int n) {
23     int i,len,pos;
24     b[1]=a[1];
25     len=1;
26     for(i=2; i<=n; i++) {
27         if(a[i]>=b[len]) {
28             len=len+1;
29             b[len]=a[i];
30         } else {
31             pos=Serch(a[i],1,len);
32             b[pos]=a[i];
33         }
34     }
35     return len;
36 }
37 
38 int main() {
39     int n;
40     while(~scanf("%d",&n)) {
41         for(int i=1; i<=n; i++)
42             scanf("%d",&a[i]);
43         printf("%d
",Dp(n));
44     }
45 }

View Code