【Codeforces 568E】Longest Increasing Subsequence | Mrsrz's blog

动态规划。

题目大意：

给定一个数列 $a_1,a_2,\ldots,a_n$，其中有 $k$ 个位置空缺。

给定 $m$ 个数 $b_1,b_2,\ldots,b_m$，可以用其中 $k$ 个数来补充空缺。每个数只能用一次。

要求最终数列的最长严格上升子序列长度最大。

输出方案。

题解：

由于要求最长严格上升子序列，所以重复使用一个数并不会使答案变大，所以转移的时候可以忽略只能使用一次的条件。

考虑到 $k$ 比较小，我们直接使用单调队列的 $O(n\log n)$ 做法来 dp。对于一个空缺位置，用 $m$ 个数都进行转移。时间复杂度 $O(n\log n+mk\log n)$。我们可以对 $b$ 排序后使用双指针来转移，则时间复杂度 $O(n\log n+mk)$。

考虑求方案。

由于空间不够，我们没法直接记录所有状态。我们可以对每个非空位，记录它上一位的位置。

如果上一位是非空缺位置，则直接往前跳。

如果上一位是空缺位置，我们直接枚举上一个非空缺的位置。假设当前位置为 $j$，枚举到的非空缺位置为 $i$，$a_{i+1..j-1}$ 之间有 $A$ 个空位，$b$ 中有 $B$ 个数在 $(a_i,a_j)$ 里。

令 $f_k$ 表示位置 $k$ 结尾的最长上升子序列长度。如果满足 $f_i+min(A,B)+1=f_j$，则 $j$ 可以从 $i$ 转移过来。这是一定存在的。

剩下的无关空位用没有用过的数随便填即可。

时间复杂度 $O(n\log n+(n+m)k)$。

Code：

#include<cstdio>
#include<algorithm>
#include<functional>
#include<set>
#include<cstring>
using namespace std;
const int N=1e5+6;
int n,a[N],b[N],m,h[N],t,f[N];
int pre[N],pos[N];
multiset<int>st;
set<int>sst;
int main(){
    memset(pre,-1,sizeof pre);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    scanf("%d",&m);
    for(int i=1;i<=m;++i)scanf("%d",b+i),st.insert(b[i]),sst.insert(b[i]);
    sort(b+1,b+m+1,greater<int>());
    a[0]=-2e9;
    a[n+1]=2e9;
    f[0]=0,h[0]=t=0;
    for(int i=1;i<=n+1;++i)if(a[i]!=-1){
        int it=lower_bound(h,h+t+1,a[i])-h;
        if(it>t)++t;
        f[i]=it,h[it]=a[i],pos[it]=i,pre[i]=pos[it-1];
    }else{
        h[t+1]=2e9;
        for(int i=1,it=t+1;i<=m&&it;++i){
            while(it&&h[it-1]>=b[i])--it;
            if(it)h[it]=b[i],pos[it]=-1;
        }
        if(h[t+1]<2e9)++t;
    }
    reverse(b+1,b+m+1);
    m=unique(b+1,b+m+1)-b-1;
    for(int it=n+1;it;){
        int pr=pre[it];
        if(pr!=-1&&a[pr]!=-1)it=pr;else{
            int A=0,B=0;
            for(int i=it-1;~i;--i)if(a[i]!=-1){
                int nw=a[i];
                if(nw>=a[it])continue;
                B=lower_bound(b+1,b+m+1,a[it])-upper_bound(b+1,b+m+1,a[i]);
                if(f[i]+1+min(A,B)==f[it]){
                    int Pre=a[i];
                    for(int j=i+1;j<it;++j)
                    if(a[j]==-1&&A&&B){
                        --A,--B;
                        auto iter=sst.upper_bound(Pre);
                        a[j]=Pre=*iter;
                        st.erase(st.find(*iter));
                        sst.erase(iter);
                    }
                    it=i;
                    break;
                }
            }else ++A;
        }
    }
    for(int i=1;i<=n;++i)
    if(a[i]==-1)a[i]=*st.begin(),st.erase(st.begin());
    for(int i=1;i<=n;++i)
    printf("%d ",a[i]);
    return 0;
}