【全网首发】洛谷P1020 [NOIP1999 提高组] 导弹拦截

发布时间:2023年12月23日

P1020 导弹拦截 の 题目传送门。

解题思路

显然,第一问求的是最长不上升子序列。

于是接下来直接抛开第一问不谈,也不考虑优化,直接考虑第二问。待会就知道原因了。

引理:Dilworth 定理

狄尔沃斯定理亦称偏序集分解定理,该定理断言:对于任意有限偏序集,其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真,它断言:对于任意有限偏序集,其最长链中元素的数目必等于其最小反链划分中反链的数目。

该定理在该问题上可以理解成:把序列分成不上升子序列的最少个数,等于序列的最长上升子序列长度。把序列分成不降子序列的最少个数,等于序列的最长下降子序列长度。

则第二问等价于最长上升子序列。

贪心

先不管引理对我们有什么用,我们直接思考第二问贪心怎么做。

对于每个数,既可以把它接到已有的导弹拦截后面,也可以建立一个新系统。要使子序列数最少,应尽量不建立新序列。

另外,应让每个导弹系统的末尾尽可能大,这样能接的数更多。因为一个数若能接到小数后面,必然能接到大数后面,反之则不成立。根据这些想法,可总结出如下贪心流程:

从前往后扫描每个数,对于当前数

1.若现有子序列的结尾都小于它,则创建新子序列。

2.否则,将它放到结尾大于等于它的最小数后

贪心证明

我们可以知道,证明 A=B,可证 A≤B?且 A≥B。

记?A?为贪心解,B?为最优解。

贪心解能覆盖所有数,且形成的都是不升序列,因此合法。由定义,B≤A。

假设最优解对应的方案和贪心方案不同,从前往后找到第一个不在同一序列的数?x。假设贪心解中?x?前面的数是?a,最优解中?x?前面的数是?b,a?后面的数是?y,由于贪心会让当前数接到大于等于它的最小数后面,所以?,x,y≤a≤b。
此时,在最优解中,把?x?一直到序列末尾,和?y?一直到序列末尾交换位置,这样做不影响正确性,也不增加序列个数,但会使?x?在最优解和贪心解中所处的位置相同。由于序列中的数是有限的,只要一直做下去,一定能使最优解变为贪心解。因此A≤B。

等等,第二问根据引理是求最长上升子序列,但是贪心也可以求。说明我们的贪心解法等于最长上升子序列 !!(引理作用即在此处

贪心可以求上升子序列,自然连第一问求的最长不上升子序列也可以求了。

最坏复杂度O(n2),但是数据很水,可以完美通过此题。

我们也可以对此代码进行二分优化(即查找?k?的时候):

AC 代码:

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
const int MAXN=1e5+3;
int n,t,H[MAXN],F[MAXN];
int main(){
    while(~scanf("%d",&H[++n])); --n;
    t=0,memset(F,0,sizeof(F)),F[0]=INF;
    up(1,n,i){
        int l=0,r=t+1; while(r-l>1){
            int m=l+(r-l)/2;
            if(F[m]>=H[i]) l=m; else r=m;
        }
        int x=l+1;  // dp[i]
        if(x>t) t=x; F[x]=H[i];
    }
    printf("%d\n",t);
    t=0,memset(F,0,sizeof(F)),F[0]=0;
    up(1,n,i){
        int l=0,r=t+1; while(r-l>1){
            int m=l+(r-l)/2;
            if(F[m]<H[i]) l=m; else r=m;
        }
        int x=l+1;
        if(x>t) t=x; F[x]=H[i];
    }
    printf("%d\n",t);
    return 0;
}

文章来源:https://blog.csdn.net/2301_81328824/article/details/135164484
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。