题解：P14556 [ROI 2013 Day2] 星际航程

c2024008 · 2026-11-11 16:47:58 · 题解

P14556 [ROI 2013 Day2] 星际航程

提供一个不一样的思路。

令最大的 l_i 使得 a_{l_i}=a_i。把所有数对 (l_i,i) 看作线段，便可以把问题转化为求最小线段覆盖数使得整个数列被覆盖。设 dp_i 为第 i 位作为线段终点的最小覆盖数，容易得出方程 dp_i=\min\{dp_j+1\} 其中 j \in [l_i,i)。

朴素转移是 O(n^2) 的时间复杂度。考虑优化。注意到 dp_i 下标越大且值越小更有价值，可以放进单调栈里维护，查询时二分下标满足约束条件即可。总时间复杂度 O(n \log n)。路径输出略微有些麻烦，可以用 f_i 记录从哪一个线段末尾转移而来，输出 l_{f_i} 即可。

code

#include<iostream>
#include<vector>
using namespace std;
const int N=3e5+5;
int a[N],las[N],L[N],dp[N],st[N],tt,f[N],n;
vector<int>p;
void path(int id){
    p.push_back(id);
    if(id==1) return;
    path(f[id]);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        L[i]=las[a[i]];
        las[a[i]]=i;
    }
    dp[1]=0;st[++tt]=1;
    for(int i=2;i<=n;i++){
        int l=1,r=tt,ans=i;
        if(!L[i]){//不可做为线段终点
            dp[i]=1e9;
            goto EN;
        }
        while(l<=r){
            int mid=(l+r)>>1;
            if(st[mid]>=L[i])
                r=mid-1,ans=min(ans,st[mid]);
            else l=mid+1;
        }
        f[i]=ans;
        dp[i]=dp[ans]+1;
        EN:;
        while(tt>0&&dp[st[tt]]>=dp[i]) --tt;
        st[++tt]=i;
    }
    if(dp[n]>=1e9){
        cout<<0;
        return 0;
    }
    cout<<dp[n]<<'\n';
    path(n);
    for(int i=p.size()-2;i>=0;i--)//注意不用输L[1]，并且要倒着输
        cout<<L[p[i]]<<' ';
    return 0;
}