本文为题解集

O1759 最长上升子序列
X1259 【例9.3】求最长不下降序列
P1020 导弹拦截

orz 核心代码都基于大佬 $\color{black}{\texttt{z}}\color{red}{\texttt{zd}}$ 当时提出的 $O(n \log n)$ 的解法 tql。

O1759 最长上升子序列

code

先 $po$ 一下 $\color{red}{\text{code:}}$

#include<cstdio>
#include<iostream>
int n,f[2000],a[2000],ans=1;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	f[1]=a[1];
	for(int i=2;i<=n;i++)
	{
		int l=1,r=ans;
		while(l<=r)
		{
		    int mid=(l+r)>>1;
			if(f[mid]>=a[i]) r=mid-1;
			else l=mid+1;
		}
		ans=std::max(ans,l),f[l]=a[i]; 
	}
	printf("%d",ans);
	return 0;
}//orz短小精悍

废话警告

2019 年 12 月 7 日上午，集训室。

教练开始讲线性 dp，以此题为例。

教练：“谁能提供此题的一种解法？”

$\color{black}{\texttt{z}}\color{red}{\texttt{zd}}$ ：“可以这样…blabla”。

思路：

“这是基于贪心的（？）。我们可以开两个数组，a[] 和 f[]。”

“其中 a[] 存储原数据，f[] 存储当前的最长上升子序列。”

“ $a_1$ 先要赋值给 $f_1$ ，作为队头。”

“假设要将 $a_2$ 压入，且 $a_2 > f_1$ ，则 $f_2=a_2$ 。”

教练：“嗯。”

“假设又要将 $a_3$ 压入，且若 $a_3 < f_1$ ，则 $f_1=a_3$ 。”

教练：“这样你的 f[] 数组不就破坏了？”

“不不不。对于这道题，我们只需维护 ans 的值即可。”

教练：“如果要将 $a_4$ 压入，且 $f_2>a_4>f_1$ ，怎么办？”

“让 $f_2=a_4$ ，即将 f[] 数组中比 $a_4$ 大的数中最小的数赋值。”

“这样可以通过对 f[] 二分查找，找到比 $a_4$ 大的数中，最小的数，即 $f_2$ 。”

大佬 $\color{black}{\texttt{z}}\color{red}{\texttt{zy}}$ ：“或许我能把你 hack 掉。比如这组数据：6,7,8,9,1,2,3,4,5。”

“好…blabla”

首先：

a: 6 7 8 9 1 2 3 4 5
f: 6

把7压入：

f: 6 7

以此类推：

f: 6 7 8 9
ans: 4

把1压入：

f: 1 7 8 9  <== f[1]=a[5]
ans: 4

把2压入：

f: 1 2 8 9
ans: 4

以此类推：

f: 1 2 3 4
ans: 4

把5压入：

f: 1 2 3 4 5
ans: 5

完美

大佬 $\color{black}{\texttt{z}}\color{red}{\texttt{zy}}$ ：“这组：1,9,2,8,3,7,4,6,5。”

首先：

a: 1 9 2 8 3 7 4 6 5
f: 1

把1,9压入：

f: 1 9
ans: 2

把2压入：

f: 1 2  <== f[2]=a[3]
ans: 2

把8压入：

f: 1 2 8
ans: 3

把3压入：

f: 1 2 3 <== f[3]=a[5]
ans: 3

以此类推：

f: 1 2 3 4 5
ans: 5

Perfect.

教练：“我好像举不出反例。你的做法应该是 $O(n log n)$ 的。”

“（他在 fake 了）如果谁能举出反例或证明我的做法是错误的，请在下方评论！”（这不就是 Yurchiu 说的吗

update：大佬 $\color{black}{\texttt{z}}\color{red}{\texttt{zd}}$ 已亲自手写了一份证明。Yurchiu 借鉴此大佬的证明过程：

证明：最长上升子序列使用以上算法的正确性。

设原序列 $S=\{a_1,a_2,a_3,...,a_n\}$ ，目前的最长上升子序列 $F=\{b_1,b_2,...,b_{ans}\}$ 且单调递增（其中 ans 指最长上升子序列的长度）。

一种情况：

对于 $S$ 中的一个元素 $a_x$ ，如果 $∀i∈F$ ， $a_x>i$ ，则将 $a_x$ 置于 $F$ 序列末尾， $ans\gets ans+1$ 。这样是最优的。

否则：

$F$ 中必定有一个对应的 $b_y$ ，在满足 $a_x<b_y$ 的条件下最小。

那么，用 $a_x$ 替换 $b_y$ （ $b_y\gets a_x$ ）与否，对目前解是无影响的。

对于 $F$ 中的一个子串 $f=\{b_i,b_{i+1},...,b_j\}$ ，显然 $b_j$ 值越小，就可以有更多的元素排在子序列 $f$ 之后，对于全局是有可能更优的。

考虑 $b_y$ 就是这里的 $b_j$ ，因此， $b_y\gets a_x$ 不会使全局解变得更差。这样 $F$ 中不是真正的最长上升子序列，但 ans 是最长上升子序列的长度。

综上所述， $∀i\in S$ ，采用以上策略，可以使 ans 达到最优。

命题得证。

请 dalao 们尽情轻喷上述证明过程。

X1259 【例9.3】求最长不下降序列

here

先 po 一下 $\color{red}{\text{code}}$ ：

#include<cstdio>
#include<iostream>
int n,f[2000],a[2000],ans=1,q[2000];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	f[1]=a[1];
	for(int i=2;i<=n;i++)
	{
		int l=1,r=ans,tmp=ans;
		while(l<=r)
		{
		    int mid=(l+r)>>1;
			if(f[mid]>a[i]) r=mid-1;//坑点：最长 ***不下降*** 序列
			else l=mid+1;
		}
		ans=std::max(ans,l),f[l]=a[i]; 
		if(ans!=tmp)
			for(int i=1;i<=ans;i++)
				q[i]=f[i];
	}
	printf("max=%d\n",ans);
	for(int i=1;i<=ans;i++)
		printf("%d ",q[i]);
	return 0;
}

思路：

教练：“这样你的 f[] 数组不就破坏了？”

“不不不。对于这道题，我们只需维护 ans 的值即可。”

那如何得到正确的 f[] 数组呢？

显然，当 ans 变化时，f[] 就是当前的最长公共子序列。

所以只需把它 copy 一下即可。

最坏情况每次都会 copy 一次， $O(n^2)$ 。

P1020 导弹拦截

here

先 po 一下 $\color{red}{\text{code}}$ ：

#include<bits/stdc++.h>
using namespace std;
int n=0,f1[200000],f2[200000],a[200000],ans1,ans2;
int main()
{
	while(scanf("%d",&a[++n])!=-1);n--;
	memset(f1,0,sizeof(f1)),ans1=1,f1[1]=a[1];
	memset(f2,0,sizeof(f2)),ans2=1,f2[1]=a[1];
	for(int i=2;i<=n;i++)
	{
		int l=1,r=ans1;
		while(l<=r)
		{
		    int mid=(l+r)>>1;
			if(f1[mid]<a[i]) r=mid-1;
			else l=mid+1;
		}
		ans1=max(ans1,l),f1[l]=a[i]; 
		l=1,r=ans2;
		while(l<=r)//卡常
		{
		   	int mid=(l+r)>>1;
			if(f2[mid]<a[i]) l=mid+1;
			else r=mid-1;
		}
		if(f2[l])
			f2[l]=a[i];
		else
			f2[++ans2]=a[i];
	}
	printf("%d\n%d",ans1,ans2);
	return 0;
}