• 周五. 7月 1st, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

【LG P1233】木棍加工

admin

11月 28, 2021

前置知识——最长上升子序列

什么是最长上升子序列? 就是给你一个序列,请你在其中求出一段不断严格上升的部分,它不一定要连续。当 (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(nlog_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
",len);    
    return 0;
}

简析

这道题首先要用结构体排序,以木棍的长度为第一关键字(从大到小),以宽度为第二关键字排序(同样也是从大到小)。

需要注意的是,如果在两根木棍长度相等的情况下,必须要按宽度排序,否则就会被 hack。

如果是在同一次准备周期里面,前面的木棍一定在后面木棍之前被加工。

这样,这个问题就转化成了在 (n) 个数中,求不下降子序列最少个数。

根据 ( ext{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;
}

参考资料

知识共享许可协议

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。

限于本人水平,如果文章有表述不当之处,还请不吝赐教。

发表评论

您的电子邮箱地址不会被公开。