[USACO04OPEN]The Cow Lineup

· · 题解

这题是被换了么，为啥感觉题解和题面讲的不是同一个东西？/qd

题意简述

给你一个值域为 k 的长度为 n 的序列，求不是这个序列的子序列的最短长度。

Solution

双倍经验

输出方案是简单的，考虑这两题的差别就是数据范围。

先大概来康康当值域小的时候的做法。也就是上面那题。考虑 dp。

我们令 dp_i 表示 [i,n] 中没有出现的子序列的最短长度。那么如果当前后缀中有某一个值没有出现过，那么 dp_i=1；否则，我们枚举这个没有出现过的子序列的第一个数，令它在后缀中从前往后第一次出现的位置为 j，那么就相当于从 dp_{j+1} 转移过来，即：dp_i=dp_{j+1}+1。在值域小的情况下，可以预处理一个数组 nxt_{i,j} 表示后缀 [i,n] 中 j 从前往后第一次出现的位置。然后直接从后往前做，这样复杂度是 O(nk) 的。

这题能获得 92pts。

现在我们考虑优化这个东西。实际上，这个 dp_i 转移的时候，只不过是从后面某些点转移过来，我们不妨开一个堆来存储这些值。然后滚动掉 nxt，即令 nxt_i 表示当前 i 第一次出现的位置，然后当 nxt_i 更新的时候，在堆中删去 dp_{nxt_i+1}+1，然后修改后重新加入。这样复杂度就变成了 O(n\log k)。

一个小问题就是我们希望这个堆能够删除某个特定的值，那就开两个堆，然后要删除一个元素就将其加入到第二个堆中，查询的时候，如果两个堆对顶相同就同时弹出即可。

Code

#include<bits/stdc++.h>
#define inf (1<<30)
#define INF (1ll<<60)
#define pb emplace_back
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pt(a) cerr<<#a<<'='<<a<<' '
#define pts(a) cerr<<#a<<'='<<a<<'\n'
#define int long long
using namespace std;
struct Heap{
    priority_queue<int,vector<int>,greater<int>> q,del;
    void push(int v){q.push(v);}
    void pop(int v){del.push(v);}
    int top(){
        while(!q.empty()&&!del.empty()&&q.top()==del.top())
            q.pop(),del.pop();
        return q.top();
    }
}q;
const int MAXN=1e5+10;
int dp[MAXN],nxt[MAXN],c[MAXN];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,k;cin>>n>>k;
    rep(i,1,n) cin>>c[i];
    rep(j,1,k) nxt[j]=-1;
    memset(dp,0x3f,sizeof(dp));
    int cnt=0;
    per(i,n,1){
        if(nxt[c[i]]==-1) cnt++;
        else q.pop(dp[nxt[c[i]]+1]+1);
        nxt[c[i]]=i;
        q.push(dp[nxt[c[i]]+1]+1);
        dp[i]=(cnt==k?q.top():1);
    }cout<<dp[1];
    return 0;
}