洛谷P1233 木棍加工题解 LIS

突然发现自己把原来学的LIS都忘完了,正好碰见这一道题。|-_-|

\(LIS\),也就是最长上升子序列,也就是序列中元素严格单调递增,这个东西有\(n^{2}\)和\(nlog_{2}n\)两种算法,其原理我就不多说了。

注意,本题的一个要点,就是不下降连续子序列的个数等于最长上升子序列的长度。

证明?由Dilworth定理可得证。

什么是Dilworth定理?它的定义是在:有穷偏序集中,任何反链最大元素数目等于任何将集合到链的划分中链的最小数目。一个关于无限偏序集的理论指出,在此种情况下,一个偏序集具有有限的宽度w,当且仅当它可以划分为最少w条链

懵逼了吗?好吧,这是它的通俗解释:就是不下降连续子序列的个数等于最长上升子序列的长度。

Dilworth定理的证明?反正我是不会,问度娘去吧。

还有,在本题中,因为有两个变量,我们只需要先按其中一个(我是按的l)作为关键字排序,然后对排序后的序列求LIS长度就行了。

其余的东西看代码吧:

#include <iostream>
#include <algorithm> using namespace std; int n, d[5005]; struct S{ //stick
int l, w;
}s[5005]; int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> s[i].l >> s[i].w;
sort(s+1, s+n+1, [](const S& a, const S& b) { \\c++11 lamda表达式
return a.l > b.l;
});
d[1] = s[1].w;
int len = 1;
for(int i = 2; i <= n; i++) {
if(d[len] < s[i].w) d[++len] = s[i].w;
else {
int p = lower_bound(d+1, d+len+1, s[i].w)-d; \\STL中的二分查找
d[p] = s[i].w;
}
}
cout << len;
return 0;
}
上一篇:Python新手学习基础之数据类型——数字类型


下一篇:Bilinear CNN与 Randomly Wired Neural Network