最长上升子序列

关于最长上升子序列的链接：

http://wenku.baidu.com/view/fe0deecea1c7aa00b52acb71.html

http://blog.sina.com.cn/s/blog_4b1e4fe9010098af.html

http://www.cnblogs.com/celia01/archive/2012/07/27/2611043.html

裸的最长上升子序列：时间复杂度为O（n*n）

POJ 2533

贴代码：

 1 #include<cstdio>
 2 #define N 1005
 3 int a[N];
 4 int lis(int n)
 5 {
 6     int *dp= new int[n+1];
 7     dp[1] =1;
 8     int ans =1;
 9     for(int i=2; i<=n; ++i)
10     {
11         int mx =0;
12         for(int j=1; j<i; ++j)
13             if(a[i] > a[j] && dp[j] > mx)
14                 mx = dp[j];
15         dp[i] = mx+1;
16         if(dp[i] > ans) ans = dp[i];
17     }
18     return ans;
19 }
20 int main()
21 {
22 //    freopen("in.c","r",stdin);
23     int n;
24     scanf("%d",&n);
25     for(int i=1; i<=n; ++i)
26         scanf("%d",&a[i]);
27     printf("%d
",lis(n));
28 }

View Code

POJ 1631 求题意，反正大家都说是求最长上升子序列。

贴代码：复杂度，O（nlogn）,超短的代码长度

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define INF 0x3f3f3f3f
 4 int dp[40005];
 5 using namespace std;
 6 int main()
 7 {
 8 //    freopen("in.c","r",stdin);
 9     int t;
10     scanf("%d",&t);
11     while(t--)
12     {
13         int n,a;
14         scanf("%d",&n);
15         fill(dp,dp+n,INF);
16         for(int i=0; i<n; ++i)
17         {
18             scanf("%d",&a);
19             *lower_bound(dp,dp+n,a) = a;
20         }
21         printf("%d
",lower_bound(dp,dp+n,INF)-dp);
22     }
23     return 0;
24 }

View Code

手动写二分的代码：

 1 #include <cstdio>
 2 int D[40005];
 3 int bs(int low,int high,int m)
 4 {
 5     int mid = (low+high)/2;
 6     while(low<=high)
 7     {
 8         if(D[mid] < m && D[mid+1] >= m) return mid;
 9         else if(D[mid] < m) low = mid+1;
10         else high = mid-1;
11         mid =  (low+high)/2;
12     }
13     return mid;
14 }
15 int main()
16 {
17 //    freopen("in.c","r",stdin);
18     int t;
19     scanf("%d",&t);
20     while(t--)
21     {
22         int n,a;
23         scanf("%d",&n);
24         scanf("%d",&a);
25         D[1]  = a;
26         int len =1;
27         for(int i=1; i<n; ++i)
28         {
29             scanf("%d",&a);
30             if(a > D[len])
31                 D[++len] = a;
32             else
33             {
34                 int j=bs(1,len,a);
35                 D[j+1] = a;
36             }
37         }
38         printf("%d
",len);
39     }
40     return 0;
41 }

View Code

codeforces 4D：

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=29608#problem/A

只留下那些宽和高都严格大于卡片的信封，如果一张都没剩下，输出0，否则，先将卡片按width的值顺序，hight的值逆序排。然后按照高度值求一次最长上升子序列，记录路径即可···

贴代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define N 5005
 6 int path[N];
 7 struct card
 8 {
 9     int w,h,ind;
10 } p[N];
11 int cmp(card a,card b)
12 {
13     if(a.w == b.w) return a.h > b.h;
14     return a.w<b.w;
15 }
16 int lcs(int n)
17 {
18     int *dp = new int[n+1];
19     dp[1] = 1;
20     int ans = 1;
21     int e =1;
22     for(int i=2; i<=n; ++i)
23     {
24         int mx =0,v=0;
25         for(int j=1; j<i; ++j)
26         {
27             if(dp[j] > mx && p[i].h > p[j].h)
28             {
29                 mx = dp[j];
30                 v  = j;
31             }
32         }
33         dp[i] = mx+1;
34         path[i] =v;
35         if(dp[i] > ans)
36         {
37             ans = dp[i];
38             e = i;
39         }
40     }
41     printf("%d
",ans);
42     return e;
43 }
44 void dfs(int x)
45 {
46     if(!x) return;
47     dfs(path[x]);
48     if(path[x]) printf(" ");
49     printf("%d",p[x].ind);
50 }
51 int main()
52 {
53 //    freopen("in.c","r",stdin);
54     int n,cnt=0,w0,h0,w,h;
55     scanf("%d%d%d",&n,&w0,&h0);
56     for(int i=1; i<=n; ++i)
57     {
58         int w,h;
59         scanf("%d%d",&w,&h);
60         if(w > w0 && h > h0)
61         {
62             ++cnt;
63             p[cnt].w = w,p[cnt].h = h,p[cnt].ind =i;
64         }
65     }
66     sort(p+1,p+cnt+1,cmp);
67     if(!cnt) printf("0
");
68     else
69     {
70         int e = lcs(cnt);
71         dfs(e);
72     }
73     return 0;
74 }

View Code

POJ 1887 最长不降子序列

贴代码：

 1 #include <cstdio>
 2 int D[40005];
 3 int bs(int low,int high,int m)
 4 {
 5     int mid = (low+high)/2;
 6     while(low<=high)
 7     {
 8         if(D[mid] > m && D[mid+1] <= m) return mid;
 9         else if(D[mid] > m) low = mid+1;
10         else high = mid-1;
11         mid =  (low+high)/2;
12     }
13     return mid;
14 }
15 int main()
16 {
17 //    freopen("in.c","r",stdin);
18     int a;
19     int cas=0;
20     while(true)
21     {
22         scanf("%d",&a);
23         if(a == -1) break;
24         D[1]  = a;
25         int len =1;
26         while(true)
27         {
28             scanf("%d",&a);
29             if(a == -1) break;
30             if(a <= D[len])
31                 D[++len] = a;
32             else
33             {
34                 int j=bs(1,len,a);
35                 D[j+1] = a;
36             }
37         }
38         printf("Test #%d:
  maximum possible interceptions: %d

",++cas,len);
39     }
40     return 0;
41 }

View Code