JOI 2025 Final T4 Sol

· · 题解

比较神的题。

你把最小覆盖刻画成最长下降就寄了。因为这样没有啥比较好的性质来贪心。

反而我们可以考虑，对于选定的一些数应该怎么做。我们从左往右每次加入一个数，如果存在一个小于等于它且最大的数，就将这个数贪心替换，否则新开一个位置。

发现这样你维护的集合里面不太会有重复的数。所以状态只有 2^V 个。然后加入一个数之后得到的状态是可以算出来的。

于是相当于我们可以设计出朴素的 \Theta(n2^V) dp：f_{i,S} 表示到达 i 并且选中它，当前状态能否是 S。

事实上，对于每个 S，我们只关心一个最大的 i 使得 f_{i,S}=1。考虑重设状态为 f_S 为最终状态为 S，最远能够到达哪里。

转移有自环。我们发现事实上需要先处理自环，这样才能保证之后的转移是优的。那自环的转移在干什么事情呢：找到第一个 a_i,a_{i+1}\not\in S 的位置 i。

暴力预处理是 nV^2，还能再给力一点吗？考虑预处理出：

  1. 每个位置往后第一个某个值 j 的位置。
  2. 每个位置往后第一个相邻二元组形如 (a_i,j) 的位置。

那么我们就可以 \Theta(1) 查询的同时做到 \Theta(nV) 预处理。然后至于非自环的转移就只有 i+1,i+2，比较简单。总复杂度 \Theta(nV+V^22^V)。

void fake_main() {
    n = read();
    rep(i, 1, n) a[i] = read(), V = max(V, a[i]), --a[i];
    rep(S, 0, (1 << V) - 1) rep(i, 0, V - 1) {
        int msk = S & ((1 << i + 1) - 1);
        if (!msk) trans[S][i] = S | (1 << i);
        else trans[S][i] = (S ^ (1 << __lg(msk))) | (1 << i);
    }
    rep(i, 0, V - 1) nxt1[n + 1][i] = nxt2[n + 1][i] = n + 1;
    per(i, n, 0) {
        rep(j, 0, V - 1) nxt1[i][j] = nxt1[i + 1][j];
        if (i) nxt1[i][a[i]] = i;
    }
    per(i, n, 1) {
        rep(j, 0, V - 1) nxt2[i][j] = nxt2[nxt1[i + 1][a[i]]][j];
        if (i < n) nxt2[i][a[i + 1]] = i;
    }
    rep(S, 0, (1 << V) - 1) {
        int tmp = n + 1;
        rep(i, 0, V - 1) {
            if (S >> i & 1) continue;
            rep(j, 0, V - 1) {
                if (S >> j & 1) continue;
                tmp = min(tmp, nxt2[nxt1[f[S]][i]][j]);
            }
        }
        f[S] = max(f[S], tmp - 1);
        if (f[S] + 1 <= n) f[trans[S][a[f[S] + 1]]] = max(f[trans[S][a[f[S] + 1]]], f[S] + 1);
        if (f[S] + 2 <= n) f[trans[S][a[f[S] + 2]]] = max(f[trans[S][a[f[S] + 2]]], f[S] + 2);
    }
    rep(S, 0, (1 << V) - 1) if (f[S] >= n - 1) ans = min(ans, (int) __builtin_popcount(S));
    write(ans);
}