hdu 1950 最长上升子序列（lis） nlogn算法【dp】

这个博客说的已经很好了。http://blog.csdn.net/shuangde800/article/details/7474903

简单记录一下自己学的：

问题就是求一个数列最长上升子序列的长度。

如果子序列长度相同，那么末尾小的子序列更有可能成为最长的子序列。所以就用一个l数组存当子序列长度为len时最小的末尾元素。如果序列下一个值比l[len]大，说明上升子序列长度增加，那么l[len++]=a[i];如果是小，就想办法把它插入到了l数组中....

HDU 1950 说白了就是求lis：

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn=40005;
 5 int a[maxn],l[maxn];
 6 int len,n;
 7 
 8 int lis()
 9 {
10     len=1;
11     l[0]=a[0];
12     for (int i=1;i<n;i++){
13         if(a[i]>l[len-1])
14             l[len++]=a[i];
15         else
16             *lower_bound(l,l+len,a[i])=a[i];
17     }
18     return len;
19 }
20 
21 int main()
22 {
23     int T;
24     cin>>T;
25     while(T--)
26     {
27         cin>>n;
28         for (int i=0;i<n;i++)
29             cin>>a[i];
30         cout<<lis()<<endl;
31     }
32     return 0;
33 }

这个是二分写法（感觉二分用的最广）：

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn=40005;
 5 int a[maxn],l[maxn];
 6 int len,n;
 7 
 8 int bin_search(int key)
 9 {
10     int left, right, mid;
11     left = 1, right = len;//应该是数据比较水，这样写是左闭右开区间查找，严格来说应该是right=len+1
12     while (left<right)
13     {
14         mid = (left + right) >> 1;
15         if (l[mid] >= key)
16             right = mid;
17         else left = mid + 1;
18     }
19     return left;
20 }
21 
22 int lis()
23 {
24     len = 1;
25     l[1] = a[1];
26     for (int i = 2; i <= n; i++) {
27         if (a[i] > l[len])
28             l[++len] = a[i];
29         else {
30             int pos = bin_search(a[i]);
31             l[pos] = a[i];
32         }
33     }
34     return len;
35 }
36 
37 int main()
38 {
39     int T;
40     cin >> T;
41     while (T--)
42     {
43         cin >> n;
44         for (int i = 1; i <= n; i++)
45             cin >> a[i];
46         cout << lis() << endl;
47     }
48     return 0;
49 }

二分也可以这样写（查找第一个大于或等于key的元素）：

 1 int bin_search(int key)
 2 {
 3     while(left<=right)
 4     {
 5         mid=(left+right)>>1;
 6         if(l[mid]>=key)
 7             right=mid-1;
 8         else left=mid+1;
 9     }
10     return left;
11 }

还有一种是用stl里的set写，原理和上面一样，感觉用的好精妙：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<set>
 4 using namespace std;
 5 const int MAXN = 40005;
 6 set<int> st;
 7 set<int>::iterator it;
 8 int a[MAXN];
 9 
10 int main()
11 {
12     int T, n;
13     cin >> T;
14     while (T--)
15     {
16         st.clear();
17         cin >> n;
18         for (int i = 1; i <= n; i++) {
19             cin >> a[i];
20             if (st.count(a[i])) continue;
21             st.insert(a[i]);
22             it = st.find(a[i]);
23             it++;
24             if (it != st.end())
25                 st.erase(it);
26         }
27         cout << st.size() << endl;
28     }
29     return 0;
30 }

当然，还有更精妙的：

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int INF = 0x3f3f3f3f;
 5 const int N = 50000;
 6 int a[N],dp[N];
 7 
 8 int main()
 9 {
10     int T, n;
11     cin >> T;
12     while (T--)
13     {
14         cin >> n;
15         for (int i = 0; i < n; i++) {
16             cin >> a[i]; dp[i] = INF;
17         }
18         for (int i = 0; i < n; i++)
19             *lower_bound(dp, dp + n, a[i]) = a[i];
20         cout << lower_bound(dp, dp + n, INF) - dp << endl;
21     }
22     return 0;
23 }

hdu 1950 最长上升子序列（lis） nlogn算法【dp】

相关推荐