先来抛个经典题目
Description
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度(雷达给出的高度数据是的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
Sample Input
389 207 155 300 299 170 158 65
Sample Output
6
2
Solution
经典的导弹拦截题目,经典的线性,设
表示以第
位置开头的最长长度,容易得出状态转移方程
,需要注意的是,
要从
循环到
,因为状态转移时需要保证
后面的
值已经预处理好才能进行转移,时间复杂度
先抛个第一问的代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include<bits/stdc++.h> using namespace std; #define N 100010 int n,a[N],dp[N],ans; int main() { scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",&a[i]),dp[i]=1; for (int i=n;i;--i) for (int j=i+1;j<=n;++j) if (a[j]<=a[i]) dp[i]=max(dp[i],dp[j]+1); for (int i=1;i<=n;++i) ans=max(ans,dp[i]); return printf("%d",ans),0; } |
关于第二问,抛开问题不谈,先来介绍一下离散数学中的几个概念和定理。
①偏序关系:设是集合
上的一个二元关系,若
满足自反性、反对称性和传递性,则称
是
上的偏序关系。
以样例输入为例,集合,则二元关系
用关系矩阵表示如下所示。
显然二元关系满足自反性、反对称性和传递性,是偏序关系。
②可比、不可比:设是一个偏序集,对于任意的
,若
或
,则称
和
可比,否则就称它们不可比。
③链、反链:设是一个偏序集,
是
的一个子集,如果
中任意两个元素可比,则
是一条链,如果
中任意两个元素不可比,则
是一条反链。
④定理:对于任意有限偏序集,其最大反链中元素的数目必等于最小链划分中链的数目。
其对偶形式:对于任意有限偏序集,其最长链中元素的数目必等于最小反链划分中反链的数目。
由此可见,题目的第二问就是求最小链划分中链的数目,而第一问我们已经求出最大链中元素的数目,所以由定理可得,我们再求出最大反链中元素的数目就是第二问的答案,只需再
一次即可。
第二问代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include<bits/stdc++.h> using namespace std; #define N 100010 int n,a[N],dp[N],ans; int main() { scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",&a[i]),dp[i]=1; for (int i=1;i<=n;++i) for (int j=1;j<i;++j) if (a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1); for (int i=1;i<=n;++i) ans=max(ans,dp[i]); return printf("%d",ans),0; } |
至于定理的证明,这里便不再赘述,有时间会写一篇总结
(等想起来再说吧233)
下面介绍一下的做法(划重点!!!)
花里胡哨的方法下面有,这里先说最浅显易懂的
维护一个单调不增的单调栈,最终我们想要这个栈里存储的元素个数就是第一问的答案,那么我们每遇到一个高度时就和栈顶元素进行比较,这里我们假设该高度为
,栈顶元素为
,如果
,说明现在的高度能够直接接在栈的后面,那么我们直接
,
为栈内元素个数,如果
,发扬瞎搞精神,没有条件创造条件也要上,由于栈内元素是有序的,二分查找出栈内第一个小于等于
的元素,把这个元素踹掉换成
。
为什么这样做是正确的呢?
我们可以这样想,假设二分查找找到的第一个小于等于的元素为
,如果
在栈顶,那么直接替换就好了,因为替换后的栈顶元素工作能力比之前的强,后面可能能接上更多的元素,如果
不在栈顶,那么我们可以直接替换掉它,因为
后面不可能再用到了,既然这个位置注定存在,那么我们这里放
还是放
都无所谓。
放一个第一问的代码,第二问的代码就不需要了,按照上面的定理再用同样方法做就OK了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include<bits/stdc++.h> using namespace std; #define N 100010 int n,a[N],S[N],top; int main() { scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",&a[i]); S[++top]=a[1]; for (int i=2;i<=n;++i) if (a[i]<=S[top]) S[++top]=a[i]; else S[upper_bound(S+1,S+top+1,a[i],greater<int>())-S]=a[i]; printf("%d",top); return 0; } |
Special
多加了个模块,专门列一些大犇们的做法,真的是绝了!
法一:线段树/树状数组优化
注意到导弹的高度都是不超过的正整数,可以以导弹高度为下标建立线段树,为什么不直接以序列下标建线段树呢?我们可以看到,方程转移是有条件的,符合条件才进行转移,如果我们去判断是否能够转移,那么时间复杂度还是
,并没有起到优化的效果,所以我们只能另辟蹊径,直接以导弹高度建立线段树,这样转移的时候直接查询
的最大值即可,晚上想了好久为什么这样是正确的,万一序列里有比当前高度大且比它靠前的存在呢,结果发现这种担心完全是多余的,我们是从后往前循环,每个循环的点的状态只与序列里比它靠后的有关,虽然比它靠前的比它高度高,但是还没转移到,当然不会对当前转移产生影响。后来我又想了一个问题
(我为什么老是自己给自己找麻烦),就是这个线段树到底是建立在什么基础上的,往常我们使用线段树是直接针对想要操作的序列建的,而针对这个问题,线段树很明显是想要操作值,但是下标又是导弹高度,后来想明白对于这个序列,它的高度、序列下标和
值一体的,也就是说,我们想要操作一个
值的时候,这个
值必定对应着一个导弹高度和一个序列下标,所以我们这个线段树里面的值虽然是对应区间
值的最大值,但是我们转移的时候在循环中已经利用该
值所对应的导弹高度和序列下标作出了是否能够转移的判断,线段树的作用仅仅是转移。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include<bits/stdc++.h> using namespace std; #define N 100010 #define inf 1e9 int n,a[N],ans,node[N<<1],M; void change(int s,int l,int r,int x,int y) { int mid=(l+r)>>1; if (l==r && l==x) return node[s]=y,void(); if (x<=mid) change(s<<1,l,mid,x,y); else change(s<<1|1,mid+1,r,x,y); node[s]=max(node[s<<1],node[s<<1|1]); } int query(int s,int l,int r,int x,int y) { int mid=(l+r)>>1,temp=-inf; if (x<=l && y>=r) return node[s]; if (x<=mid) temp=max(temp,query(s<<1,l,mid,x,y)); if (y>mid) temp=max(temp,query(s<<1|1,mid+1,r,x,y)); return temp; } int main() { scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",&a[i]),M=max(M,a[i]); for (int i=n;i;--i) { int tmp=query(1,1,M,1,a[i])+1; change(1,1,M,a[i],tmp),ans=max(ans,tmp); } return printf("%d",ans),0; } |
需要注意的是,这里初始的值不是
而是
了,为什么会出现这种情况,因为之前我们状态转移的时候是以序列下标为下标进行转移的,所以并不存在重复的情况,而我们以导弹高度为下标的时候,导弹高度可能存在重复的情况,我们将初始值设为
,那么进行转移的时候,假如该点序列后面没有比该点高度小的话,那么在方程
中,
的值应该是不变的,然而
的值本身就应该是
,所以这里我们直接查询出
再加
就能满足转移方程的所有情况。
第二问就不说了,还是上面那个定理。
法二:最小路径覆盖
此法针对第二问,我们把每个导弹拦截系统能够拦截的导弹按照顺序排在一起,这些导弹构成了一条链,那么我们可以把这条链抽象到图论上,我们假设这些导弹构成了一张图,也就是说每个我们都连一条
->
的边,那么我们就能得到一张
(有向无环图),那么第二问所求的就是求
中的最小不相交路径覆盖。
首先我们需要拆点,将每个点拆成出点
和入点
,分别对应着出边和入边,然后根据导弹之间的高度关系进行连边,对于每一条边都是
向
连一条边,这样连边和原先的
是等价的,因为点与点之间的连接关系没有改变,只是把一个点拆成了入点和出点,为什么要这样连边呢?因为我们要将有向图变成二分图。
因为我们要求的最小不相交路径覆盖,而最小路径覆盖=点数-最大匹配数,为什么呢?假设我们一开始没有任何连边,那么我们要实现最小覆盖的路径数是点数
,每当我们在二分图中获得一个匹配,相当于在两个点连了一条边,那么路径数就要减
,而我们前面的拆点操作正好能够保证该点作为中介点的可能性,假设该点是中介点,正因为入点和出点正好在图的两边,它们有可能成为最大匹配方案中的两条边,那么正好能够形成一个以该点为中介点的通路,这就是把有向图变成二分图的必要性。
用网络流匈牙利算法均可,匈牙利算法的时间复杂度为,其中
是二分图中左边点的个数,
是二分图中边的个数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<bits/stdc++.h> using namespace std; #define N 100010 int n,a[N],ans,cnt,h[N<<1],part[N<<1]; struct data { int to,next; }edge[N*10]; bool used[N<<1]; void add(int u,int v) { edge[++cnt]=(data){v,h[u]},h[u]=cnt,edge[++cnt]=(data){u,h[v]},h[v]=cnt; } bool find(int x) { for (int i=h[x];i;i=edge[i].next) if (!used[edge[i].to]) { used[edge[i].to]=true; if (!part[edge[i].to] || find(part[edge[i].to])) { part[edge[i].to]=x; return true; } } return false; } int main() { scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",&a[i]),dp[i]=1; for (int i=1;i<n;++i) for (int j=i+1;j<=n;++j) if (a[i]>=a[j]) add(i,j+n); for (int i=1;i<=n;++i) { memset(used,false,sizeof(used)); if (find(i)) ++ans; } return printf("%d",n-ans),0; } |