LIS最长上升子序列

最长上升子序列：

uva,497

其实是裸的lis题目，只是需要打印输出。一开始以为打印任意最长上升子序列就可以了，之后一直wa，然后才发现是一开始的最长上升子序列，要考虑实际的应用场景。后面那个mark有点像dijkstra和union find还有lca的father。才发现这种思想已经渗透了整个算法和数据结构的方方面面。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <cstring>
 6 #include <cstdlib>
 7 
 8 using namespace std;
 9 
10 int a[10005];
11 
12 void solve(int index)
13 {
14     int mark[10005];
15     vector<int> dp(index+5,0);
16     for(int i=1;i<=index;i++)
17         mark[i]=-1;
18     
19     for(int i=1;i<=index;i++)
20     {
21         dp[i]=1;
22         for(int j=1;j<i;j++)
23         {
24             if(a[j]<a[i])
25             {
26                 if(dp[i]<dp[j]+1)
27                 {
28                     dp[i]=dp[j]+1;
29                     mark[i]=j;
30                 }
31             }
32         }
33     }
34     
35     
36     int maxAns=0,maxPos=0;
37     
38     for(int i=1;i<=index;i++)
39     {
40         if(maxAns<dp[i])
41         {
42             maxAns=dp[i];
43             maxPos=i;
44         }
45     }
46     
47     int lis[10005],k=maxPos;
48     for(int i=maxAns;i>0;i--)
49     {
50         lis[i]=a[k];
51         k=mark[k];
52     }
53     
54     printf("Max hits: %d
",maxAns);
55     for(int i=1;i<=maxAns;i++)
56         cout<<lis[i]<<endl;
57 }
58 
59 int main()
60 {
61     int m;
62     scanf("%d",&m);
63     char s[50];
64     getchar();
65     getchar();
66     
67     for(int i=0;i<m;i++)
68     {
69         int index=0;
70         while(gets(s) && s[0])
71         {
72             a[++index]=atoi(s);
73         }
74         if(i>0)
75             cout<<endl;
76         solve(index);
77     }
78     return 0;
79     
80 }

View Code

uva,437把二维将到一维度，通过排序。然后加和的lis问题

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <queue>
 6 #include <vector>
 7 using namespace std;
 8 
 9 struct node
10 {
11     int x,y,z;
12     node(){}
13     node(int x,int y,int z):x(x),y(y),z(z){}
14     bool operator<(const node& a)const
15     {
16         if(a.x==x) return y>a.y;
17         return x>a.x;
18     }
19 };
20 
21 
22 int main()
23 {
24     int n;
25     int x,y,z;
26     int cas=1;
27     while(scanf("%d",&n),n)
28     {
29         priority_queue<node> pq;
30         vector<node> vt;
31         for(int i=0;i<n;i++)
32         {
33             scanf("%d%d%d",&x,&y,&z);
34             if(x==y && x==z)
35             {
36                 pq.push(node(x,y,z));
37                 continue;
38             }
39             else
40             {
41                 pq.push(node(x,y,z));
42                 pq.push(node(x,z,y));
43                 pq.push(node(y,z,x));
44                 pq.push(node(y,x,z));
45                 pq.push(node(z,x,y));
46                 pq.push(node(z,y,x));
47             }
48             
49         }
50         
51         node now;
52         while(!pq.empty())
53         {
54             now=pq.top();
55             pq.pop();
56             vt.push_back(now);
57         }
58         int sz=vt.size();
59         vector<int> dp(sz+5,0);
60         for(int i=0;i<sz;i++)
61         {
62             dp[i]=vt[i].z;
63         }
64         
65         int res=0;
66         for(int i=0;i<sz;i++)
67         {
68             for(int j=0;j<i;j++)
69             {
70                 if(vt[j].y<vt[i].y && vt[j].x!=vt[i].x)
71                 {
72                     dp[i]=max(dp[i],dp[j]+vt[i].z);
73                 }
74             }
75             res=max(res,dp[i]);
76         }
77         
78         printf("Case %d: maximum height = %d
",cas++,res);
79         
80     }
81     return 0;
82 }

View Code

uva,10534

LIS问题的n*logn算法。其实如果正向求一次lis逆向求一次lis然后对所有 min(d1[i],d2[i])的2倍－1；

我写了两种方法，一种是stl的lower_bound的应用，简洁明了。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <climits>
 5 
 6 using namespace std;
 7 #define inf 1e9
 8 #define min(a,b) (((a)<(b))?(a):(b))
 9 #define maxn 10005
10 int main()
11 {
12     int n;
13     int a[maxn];
14     while(~scanf("%d",&n))
15     {
16         for(int i=1;i<=n;i++)
17             scanf("%d",&a[i]);
18         int d1[maxn],d2[maxn];
19         int dp[maxn];
20         fill(dp,dp+n,inf);
21         for(int i=1;i<=n;i++)
22         {
23             *lower_bound(dp,dp+n,a[i])=a[i];
24             d1[i]=lower_bound(dp,dp+n,inf)-dp;
25         }
26         
27         fill(dp,dp+n,inf);
28         for(int i=n;i>=1;i--)
29         {
30             *lower_bound(dp,dp+n,a[i])=a[i];
31             d2[i]=lower_bound(dp,dp+n,inf)-dp;
32         }
33             
34         int res=0;
35         for(int i=1;i<=n;i++)
36             if(res<min(d1[i],d2[i]))
37                 res=min(d1[i],d2[i]);
38         printf("%d
",res*2-1);
39     }
40     return 0;
41 }

View Code

这种是压栈的思想。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <climits>
 4 
 5 using namespace std;
 6 #define min(a,b) (((a)<(b))?(a):(b))
 7 #define maxn 10005
 8 int main()
 9 {
10     int n;
11     int a[maxn];
12     while(~scanf("%d",&n))
13     {
14         for(int i=1;i<=n;i++)
15             scanf("%d",&a[i]);
16         
17         int stack[maxn];
18         int d1[maxn],d2[maxn];
19         int index=0;
20         
21         stack[0]=INT_MIN;
22         
23         for(int i=1;i<=n;i++)
24         {
25             if(stack[index]<a[i])
26             {
27                 stack[++index]=a[i];
28             }
29             else
30             {
31                 int low=1,top=index;
32                 while(low<=top)
33                 {
34                     int mid=(low+top)>>1;
35                     if(stack[mid]<a[i]) low=mid+1;
36                     else top=mid-1;
37                 }
38                 stack[low]=a[i];
39             }
40             d1[i]=index;
41         }
42         
43         index=0;
44         stack[0]=INT_MIN;
45         for(int i=n;i>=1;i--)
46         {
47             if(stack[index]<a[i])
48                 stack[++index]=a[i];
49             else
50             {
51                 int low=1,top=index;
52                 while(low<=top)
53                 {
54                     int mid=(low+top)>>1;
55                     if(stack[mid]<a[i]) low=mid+1;
56                     else top=mid-1;
57                 }
58                 stack[low]=a[i];
59             }
60             d2[i]=index;
61         }
62         
63         
64         int res=0;
65         for(int i=1;i<=n;i++)
66             if(res<min(d1[i],d2[i]))
67                 res=min(d1[i],d2[i]);
68         printf("%d
",res*2-1);
69     }
70     return 0;
71 }

View Code

就像我前面总结的一样，这种方法只能求出在某个点的最长上升子序列的值但是保存在栈的序列确并非严格的在给定序列的上升子序列。只是这总思想可以运用而已。

乌龟的叠放：其实就是dp的经典问题的再利用，找到能叠放质量最大的乌龟，然后用背包问题取求解。

我dp开的动态数组也就是vector因为乌龟的最大承受能力不确定，否则会越界。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <vector>
 6 
 7 using namespace std;
 8 #define maxn 5700
 9 
10 int main()
11 {
12     char s[50];
13     int w[maxn],a[maxn];
14     int index=1;
15     int maxx=0;
16     while(gets(s) && s[0])
17     {
18         int cnt=0;
19         int c=0;
20         while(s[cnt]!=' ')
21         {
22             c=c*10+s[cnt]-'0';
23             cnt++;
24         }
25         w[index]=c;
26         while(s[cnt]==' ')
27             cnt++;
28         c=0;
29         while(s[cnt])
30         {
31             c=c*10+s[cnt]-'0';
32             cnt++;
33         }
34         a[index]=c-w[index];
35         if(a[index]>maxx)
36             maxx=a[index];
37         index++;
38     }
39     vector<int> dp(maxx+5,0);
40     
41     for(int i=1;i<index;i++)
42         for(int j=maxx;j>w[i];j--)
43         {
44             dp[j]=max(dp[j],dp[j-w[i]]+1);
45         }
46     printf("%d
",dp[maxx]);
47     dp.clear();
48     return 0;
49 }

View Code

活在现实，做在梦里。