AcWing 1010. 拦截导弹
原题链接
简单
作者:
LLY
,
2021-08-28 09:39:59
,
所有人可见
,
阅读 258
必要的注释已经加上了,包括迪尔沃思定理的证明
package 王の算法提高课回归;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Acwing1010 {
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static int N = 100010;
static String s[];
static int n;
static int h[] = new int[N], des[] = new int[N], asc[] = new int[N];
public static void main(String args[]) throws Exception{
s = reader.readLine().split(" ");
n = s.length;
for(int i = 1; i <= n ; i ++ ) h[i] = Integer.parseInt(s[i - 1]);
for(int i = 1; i <= n ; i ++ ){
des[i] = 1;
for(int j = 1; j <= i - 1; j ++ ){
if(h[i] <= h[j]) des[i] = Math.max(des[i], des[j] + 1);
}
}
int maximal = 0;
for(int i = 1; i <= n ; i ++ ) maximal = Math.max(maximal, des[i]);
System.out.println(maximal);
for(int i = 1; i <= n; i ++ ){
asc[i] = 1;
for(int j = 1; j <= i - 1; j ++ ){
if(h[i] > h[j]) asc[i] = Math.max(asc[i], asc[j] + 1);
}
}
maximal = 0;
for(int i = 1; i <= n ; i ++ ) maximal = Math.max(maximal, asc[i]);
System.out.println(maximal);
}
}
/*
这题有点意思的,因为他用到了迪尔沃思定理,或者说反链定理,我今天要把这定理陈述出来并且证明出来,2021年8月27日09:51:44
首先我们要知道什么叫做偏序集,偏序说的就是集合内元素的一种关系,这种关系如果满足自反,反对称,传递,那么就是偏序
比如<=就是一种偏序,自反性, a <= a的,反对称性,a <= b and b <= a => a = b成立的吧
传递性就更不用说了。一般直接用“<=“来表示这种偏序关系,但是要注意他不一定指的是我们通常认识的那种<=哈
那么对于X里面的任何2个元素a和b,我们知道他们要么可比要么不可比嘛,比如你可以定义偏序:a <= b当且仅当b的身高比a高并且体重比a大
那这确实是一个偏序吧,但是如果a跟b之间的关系是b的身高比a高,但是a的体重比b大,这种就不可比了嘛,至少在你定义的这种偏序之下是不可比的。
链的定义就是说首先这条链是X的子集,其次他里面任何2个元素之间都可比。
反链当然就是任何2个元素都不可比咯。
接下来就是我们很重要的定理了
定理1 假设(X, <= )是一个有限偏序集,然后最大链的长度是r,则X可以被划分成r个反链,而且不能再少了
定理2 假设(X, <= )是一个有限偏序集,然后最大反链的长度是m,则X可以被划分成m个链,而且不能再少了
很明显上面这2个定理是互相对偶的吧,其中定理2就是迪尔沃思定理了哈。
定理1的证明,首先最大链的长度是r,则你划分反链的时候这r个元素得分别属于不同的反链吧,因为一旦有2个元素属于同一个反链,那他们本来是属于同一条链里面的
说明是可比的,这就立刻跟反链的定义矛盾了。
因此我们知道反链至少要有r条。
然后我们再引入一个“极小元”的概念,所谓a是一个极小元就是说如果b <= a立刻有b = a,不会有比他更小的了就是这个意思,或者干脆就是跟他不可比。
其实在组合数学里面都是这样的,各种找“最小的”,“最大的”,“最长的”,“最短的”之类的,主要是因为组合数学里面的东西很多时候都是有限的。
有限的东西你要取最大最小什么的就很容易了,无限的就不一定有最大最小了。
好的我们从X开始,记X为X1,我们可以找到X的极小元集合为A1,有人可能会疑惑,这种A1一定存在吗?一定的呀,
你看极小元的定义嘛
a是极小元 <=> 对任意的b属于X,如果b <= a则有b = a
那存在极小元就是说存在一个a,使得对任意的b属于X,如果b <= a则有b = a
不存在就是说对于任意的a,都存在b属于X,使得b <= a并且b != a
那就相当于是说可以给X里面的元素排队了嘛,我从任何一个a0开始都会有a0 >= a1 >= a2 >= a3 >= a4 >= a5..而且他们互不相等。
然后我们知道,X是有限的集合呀,所以你这样一直排下去必然会重复的,一旦重复了那就是a >= b >= a这种了,根据偏序的反对称性就可以得到b = a
这就一路下来都是a0 = a1 = a2 = a3...了吧,矛盾了,
所以我们知道A1不是空集,很明显A1里面的元素不可比的吧,因为他们都是极小元,可比的话会推出相等的。
把X1拿掉A1之后的集合称为X2,我们知道对于任何的b ∈ X2,应该都存在a ∈ A1使得a <= b
因为首先A1里面的是极小元,所以不可能存在a ∈ A1使得 b <= a的,那会推出相等。然后如果b跟A1里面的任何一个元素都不可比的话。
我们可以分2种情况,要么就是b跟其他的所有元素也全都不可比,那这个时候b直接属于A1了吧,天然的极小元呀,会矛盾的。
或者b跟其他元素是可比的,如果那些跟b可比的元素c都是 b <= c的,那b又符合极小元的定义了吧,又不行。
所以必须要存在元素c <= b才对,那么我们知道如果c不是极小元的话又可以对c做同样的讨论,使得又存在d满足d <= c
然后如果d不是极小元的话又可以做同样的讨论,但是这种讨论不能一直下去,因为X是有限的,所以讨论到一定程度一定会存在一个a
使得a是极小元,并且a <= ... <= d <= c <= b,这又产生矛盾了吧,所以我们就知道对于X2里面任意的b,一定存在a ∈ A1使得a <= b
然后我们又可以继续把X2里面的极小元集合A2拿出来变成X3,然后一直拿下去,这种不可能可以无限拿下去的,拿到最后一定会有Xk = Ak的
剩下的元素全都是极小元这样子,为什么呢?因为X是有限的,然后你每次拿的都不是空集,那肯定最多拿n次嘛。
所以我们就知道了,极小元的集合A1 A2 ... Ak应该全都是反链,因为极小元之间不能比较的。
并且呢我们知道存在ai ∈ Ai使得a1 <= a2 <= .. ak吧,就是上面讨论过的。
所以我们就得到了一条长度是k的链,并且呢我们用k个反链把X划分好了,这说明k >= r吧,因为上面证明过了你至少得用r个反链嘛
然后又有k <= r吧,因为链的长度最多是r。所以我们知道k = r的。这就证明完毕了。
定理2就比较难证明了,要证明一个有限偏序集的最大反链长度是k的话我们可以得到偏序集可以分成k个链。
这个是对k做数学归纳法,首先当k = 1的时候,说明这个偏序集里面任何2个元素都可以比,则整个偏序集就是1个链,证明完毕。
所以假设对于所有的,最大反链< k的偏序集都有上述结论成立,我们来看最大反链长度 = k的情况,首先我们知道存在k个元素
a[1], a[2], ... a[k]形成一条反链,那我们知道这就是k条链了吧,每条链都只有1个元素。
好的假设我们现在已经用X里面的部分元素构造了k条链,并且每条链里面都有最大反链的1个元素,初始情况就像上面这个咯,a[1] ~ a[k]各自是一条链。
这k条链分别是C[1] ~ C[k],如果X里面还有其他的元素a,我们无非想证明a可以加入这k条链里面嘛,或者这些链可以变化一下,保持k条链。
那么我们把C[i]进行分解,可以分解成3个部分:1. N[i] = {x | x ∈ C[i] and x is not comparable with a} 2. L[i] = {x | x ∈ C[i] and x <= a}
3. U[i] = {x | x ∈ C[i] and x > a},要么能比,能比的话就是要么大于要么小于,要么就不能比嘛,不会有其他情况了。
很明显这上面都是严格的 > 和严格的 <,没有等号的。
我们让N = N[1] + ... N[k], U = U[1] + ... U[k],L = L[1] + ... L[k]
我们接下来证明,存在一个m,使得N + U - U[m]里面找不出长度是k的反链。
用反证法,假设对于任何j,我们都有N + U - U[j]能找出长度是k的反链,那我们知道N + U - U[j] <= C[1] + ... C[k]的
因此你在N + U - U[j]里面找出来的长度是k的反链S[j]应该满足什么?应该是这条反链在C[i]里面各占1个元素吧,因为C[i]是链啊,所以你找出来的R中不可能有2个元素同时属于同一个C[i]
那只能是每条链各一个了。所以让j变动起来得到S = S[1] + S[2] + ... S[K]的话,我们就知道由于S[j]是N + U - U[j]的子集,所以S[j]里面没有U[j]的元素
但是刚刚证明过S[j]里面又是C[1] ~ C[k]的元素各有一个,因此S[j]里面必须有1个N[j]的元素,因为C[j] = N[j] + L[j] + U[j]嘛
S[j]里面有C[j]的一个元素,但是S[j]是N + U - U[j]的子集,所有S[j]里面没有L的元素,也没有U[j]的元素,只能是有U[j]的元素咯,
所以我们就知道了S里面应该U[1] ~ U[k]里面的元素各有一个。那么我们让S ∩ C[i]会得到一条链的一小部分吧,肯定不是空的,因为刚说过了S里面有U[1] ~ U[k]的元素各一个。
既然是链的一小部分我们就可以找到其中最小的元素s[i],那我们发现了,你在N[i]里面任意取一个元素b,在U[i]里面任意取一个元素c,
我们就知道了根据定义,b跟a不可比,c是严格比a大,正因如此b不可能比c大,因为那样会导致b > c > a,就跟b和a不可比矛盾了
所以只能c > b,为什么不是b和c不可比呢?因为他们都属于C[i]这条链呀。所以我们就知道了,s[i]这个元素肯定是属于N[i]的,当然了这种有这个论断是在N[i]非空的基础上
如果N[i]是空集,那根据定义,C[i]里面任何1个元素都跟a可比了,那a直接进到C[i]里面就好,这没什么好讨论的。
好的那我们来看s[1], s[2], .. s[k]这些S ∩ C[i]得到的最小的元素,任意地取出来s[i] 和 s[j]吧,如果他们两个可比,不妨假设是s[i] >= s[j]好了
那我们知道S = S[1] + .... S[k],所以可以让s[j] ∈ S[r],注意了这个s[j]不一定是属于S[j]的呀,你看一下构造过程就知道了,s[j]属于C[j]倒是肯定的。
然后上面我们证明过,S[r]里面是C[1] ~ C[k]的元素各有一个,于是有一个t[i] ∈ S[r] and C[i],然后根据s[i]的定义我们知道t[i] >= s[i]
那么立刻得到t[i] >= s[i] >= s[j]了吧,这就跟S[r]里面的元素不可比较矛盾了,因此我们知道s[1] ... s[k]两两互不可比,然后每一个s[i]都是属于N[i]的,所以他们跟a也不可比
于是乎就得到了一个a, s[1] ... s[k]长度是k + 1的反链,就得到矛盾了。
而一切矛盾的起因是我们假设所有的j都有N + U - U[j]能取出长度是k的反链,于是我们知道存在一个m,N + U - U[m]取不出长度是k的反链,
同理我们知道存在一个n,N + L - L[n]取不出长度是k的反链
好的我们让T 是C - U[m] - L[n]中的最大反链,如果T中存在一个元素x是属于U - U[m]的,存在一个y是属于L - L[n]的,那肯定不行的嘛
因为会得到x >= a >= y的,就跟T是反链矛盾了,然后我们有N + L - L[n] + N + U - U[m] = C - U[m] - L[n]的
因此可以知道T应该是N + L - L[n]的子集或者N + U - U[m]的子集,因为如果同时又是左边又是右边就会跟T是反链矛盾嘛,上面证明过。
因此T的长度应该不到k,然后U[m] + L[n]是一整条链的呀,就是把最开始的C[m]后面一部分跟C[n]前面一部分拿过来了嘛,中间是用a作为媒介的。
所以我们就知道,C - U[m] - L[n]应该至少还有k - 1条链,不可能有k - 2条的,因为那样就意味着你是把整个C[m]和整个C[n]拿过来拼在一起了,这会跟C[m]和C[n]中各自存在反链的1个元素矛盾
因此可得,C - U[m] - L[n]里面的最大反链长度应该就是k - 1了,然后根据归纳假设他可以变成C'[1] + C'[2] + ... C'[k - 1]
再把U[m] + L[n] + {a}这一条链拿过来,就保持住了k条链了吧。证明完毕。
*/
至于说这道题目里面的偏序要怎么定义,请各位同学自己思考吧。