前置知识——最长上升子序列
什么是最长上升子序列？ 就是给你一个序列，请你在其中求出一段不断严格上升的部分，它不一定要连续。当 \(a_j<a_i(j<i)\) 且 \(f_j+1>f_i\) 时，\(f_i=f_j+1\)。
对于每一个数，他都是在可以接下去的中，从前面的最优值 \(+1\) 转移而来。通俗的来说，你肯定就是在所有能找到的里面取最好的一个，不要白不要嘛。
因此，这个算法是可以求出正确答案的。复杂度很明显，外层枚举每个数，内层枚举目前的最优值，即 \(O(n^2)\)。
那么，有没有更快的方法呢？当然有。这回要用到二分。
我们回想一下，在上面 \(O(n^2)\) 的程序中，哪些地方看起来比较费时？
没错，就是内层用于更新的循环。因为每一次他都要查找一遍，效率并不高。
回到题目，我们发现，他只要我们求长度，所以我们可以模拟一个单调栈（曾经很多参考书说这是一个栈。实际上不是严格的栈，而是一个后进入的加在末尾，然后每次可以替换掉其中元素的序列。这个序列是单调递增的，保证结果就是所求的 LIS）。
所以每遇到一个比栈顶元素大的数，就放进栈里，遇到比栈顶元素小的就二分查找前边的元素，找到一个“最应该被换掉的元素”，用新数去更新前边的元素。这个元素可能不是最优解的一部分，但是它可以使得后面还未加入的、比较小的数更有可能进入这个队列。通俗地来说，作为门槛，他本来要大于当前序列的最后一个数才能加进去；就是如果我太大了，我就乖乖呆在末尾；如果前面有一个数比我大，也就是我比你好，既然我在你后面也就是我们两者只能选其一，那我只好把你替换掉了。虽然我这临时临头换的不一定最合适，但是对于后面还有很多的人等着排进来的情况下，我给他们创造了更多机会，使得这个序列的最后一个数有可能变小，让更多的人进来。
这个算法不难证明也是正确的。因为前面每一次的枚举都换成了二分，内层的复杂度从 \(n\) 降到了 \(\log_2\)，外层不变。所以总的复杂度是 \(O(n\log_2n)\)。
这个则是二分算法的代码：
#include<cstdio>
#include<algorithm>
const int MAXN=200001;
int a[MAXN];
int d[MAXN];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
d[1]=a[1];
int len=1;
for(int i=2;i<=n;i++)
{
if(a[i]>d[len])
d[++len]=a[i];
else
{
int j=std::lower_bound(d+1,d+len+1,a[i])-d;
d[j]=a[i];
}
}
printf("%d\n",len);
return 0;
}
简析
这道题首先要用结构体排序，以木棍的长度为第一关键字（从大到小），以宽度为第二关键字排序（同样也是从大到小）。
需要注意的是，如果在两根木棍长度相等的情况下，必须要按宽度排序，否则就会被 hack。
如果是在同一次准备周期里面，前面的木棍一定在后面木棍之前被加工。
这样，这个问题就转化成了在 \(n\) 个数中，求不下降子序列最少个数。
根据 \(\text{Dilworth}\) 定理，不下降子序列最小个数等于最大上升子序列的长度。于是乎，问题又简化成求 \(n\) 个数的最大上升子序列。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
struct stick {
int l,w;
} a[N];
int f[N];
int main() {
int n;
scanf("%d",&n);
for(int i=1; i<=n; ++i) {
scanf("%d %d",&a[i].l,&a[i].w);
}
sort(a+1,a+1+n,[](stick a,stick b) {
if(a.l^b.l) return a.l>b.l;
return a.w>b.w;
}),f[1]=a[1].w;
int k=1;
for(int i=2; i<=n; ++i) {
int j=lower_bound(f+1,f+k+1,a[i].w)-f;
if(j<=k) {
f[j]=a[i].w;
} else {
f[++k]=a[i].w;
}
}
printf("%d",k);
return 0;
}
参考资料
- 动态规划算法3——最长上升子序列 - frankchenfu - 博客园
- 题解 P1233 【木棍加工】 - Aehnuwx 的博客 - 洛谷博客
- 题解 P1233 【木棍加工】 - Guoyh 的博客 - 洛谷博客