P1020 [NOIP1999 普及组] 导弹拦截 题解

· · 题解

题目传送门。

题意简述

给定若干个数，求最长不上升子序列和能够覆盖该数列的最长不上升子序列个数的最小值。

题目分析

狄尔沃斯定理亦称偏序集分解定理，是关于偏序集的极大极小的定理，该定理断言：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。——百度百科

所以，第二个问题所求等于最长上升子序列的个数。

感性理解：从一开始发现第一个大于首个最大值，该部分就不能被覆盖，这样的 m 个就构成了最长上升子序列，所以需要使用 m 个。

对于求最长不上升子序列和最长上升子序列可以使用 dp 解决。

对于第 i 个数，用 dp_i 表示在 1\le i 的范围内以 i 为最长不上升子序列的长度。考虑动态转移方程 dp_i=\max\limits_{a_j\ge a_i}\{dp_j\}+1。初始状态为 dp_1=1。最长上升子序列同理。通过这种方式转移的复杂度是 O(n^2)。但原题数据为 n\le 10^5，故这种 O(n^2) 的转移不能通过本题。

考虑优化。

引理：对于长度为 j 的不上升子序列，它的末项最高为 s_i。那么必有 s_{j+1}\le s_j。因为如果有 s_{j+1}>s_j，那么必然可以找到长度为 j 的不上升子序列的末项为 s_{j+1}，这与前面的假设矛盾。上升子序列同理。

对于最长不上升子序列，在计算 dp_i 时可以二分。当 s_j\ge a_i 时答案在 j 右侧，相反则在左侧。每次运算完毕之后，将 s_{dp_i} 更新为 a_i 表示末项最大值。最长上升子序列同理。这时的复杂度转化为 O(n\log n)。该复杂度可以通过本题。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=100050;
int a[maxn],dp[maxn],s[maxn],n=0,k,ans;
int main(){
    ios::sync_with_stdio(0);
    while(cin>>k)a[++n]=k;
    for(int i=1;i<=n;++i){
        dp[i]=1;
        int l=0,r=ans+1;
        while(r-l>1){
            int mid=(l+r)>>1;
            //在右侧
            if(s[mid]>=a[i]){
                l=mid;
            }
            //在左侧
            else {
                r=mid;
            }
        }
        dp[i]=l+1;
        s[dp[i]]=a[i];
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;ans=0;
    memset(s,0,sizeof(s));
    for(int i=1;i<=n;++i){
        dp[i]=1;
        int l=0,r=ans+1;
        while(r-l>1){
            int mid=(l+r)>>1;
            if(s[mid]<a[i]){
                l=mid;
            }
            else {
                r=mid;
            }
        }
        dp[i]=l+1;
        s[dp[i]]=a[i];
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;
    return 0;
}