题解：P10395 青蛙寻青。

· · 题解

题意

link

Subtask 1

写一个爆搜，一个颜色可以跟上一个相同，也可以是接在上一个颜色后面新开一个颜色，最后递归出口要判每个颜色是或否全部出现。

Subtask 2

显然有一个 O(n^2) 的 dp，设 f_{i,j} 表示 b 序列中前 i 个数用 j 种颜色填的最小修改次数。状态转移：

f[i][j] = min(f[i-1][j], f[i-1][j-1]) + (b[i] != c[j]);

Subtask 3

上面那个 dp 看起来没有前途，所以尝试以颜色划分阶段。

首先对相同颜色的段“缩点”，最后目标状态的 b 和 a 是相同的，为了方便处理把 a 映射成一个递增的序列。

然后 f_i 可以从 f_j + i-j+1 转移，其中 j<i，c_j\le c_i，c_i-c_j\le i-j，第三个条件相当于要留足够的位置填所有颜色。

然后问题转化为三维偏序问题，复杂度 O(n\log^2 n)。

Subtask 4

考虑在上面 dp 的基础上优化，首先我们按照颜色转移，可以确定 c_j\le c_i，然后发现 i<j 时一定不满足第三个式子，把第三个式子化为 c_i-i\le c_j-j。最后以 c_i 为第一关键字，i 为第二关键字为顺序转移，最后用树状数组优化即可。复杂度 O(n\log n)。

Code

// Problem: P10395
#include <bits/stdc++.h>
#define db double
#define ll long long
#define pc putchar
#define gc getchar
#define sz(x) ((int)x.size())
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define D(i, a, b) for (int i = (a); i >= (b); --i)
#define TM cout<<fabs(&Med-&Mbe)/1048576.0<<"MB "<<1.0*clock()/CLOCKS_PER_SEC*1000<<"ms\n"
bool Mbe;
using namespace std;
namespace IO {
#define typ ll
    inline typ rd() {
        typ x = 0; bool f = 1; char ch = gc();
        while (ch < '0' || ch > '9') { if (ch == '-') f = 0; ch = gc(); }
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
        return (f ? x : (-x));
    }
    inline void wr(typ x) {
        if (x < 0) pc('-'), x = -x;
        if (x > 9) wr(x / 10); pc(x % 10 + '0');
    }
}
using namespace IO;
// ----------------- Main Code -----------------
const int N = 2e6 + 5;
int n, m, a[N], c[N], id[N], k;
vector<int> G[N];
void upd(int p, int x) { ++p; for (int i = p; i <= m + 1; i += (i & -i)) c[i] = min(c[i], x); }
int qry(int p) { ++p; int res = 1e9; for (int i = p; i; i -= (i & -i)) res = min(res, c[i]); return res; }
int main() {
    n = rd(), m = rd();
    F(i, 1, n) {
        a[i] = rd();
        if (!id[a[i]]) id[a[i]] = ++k;
        else if (a[i] != a[i-1]) { wr(-1), pc('\n'); return 0; }
    }
    if (m < k) { wr(-1), pc('\n'); return 0; }
    F(i, 1, m) {
        int x = rd();
        G[id[x]].push_back(i);
    }
    memset(c, 0x3f, sizeof c);
    int ans = m;
    upd(0, 0);
    F(i, 1, k) {
        for (int v : G[i]) if (v >= i && m-v >= k-i) {
            int p = v - i; // 缩点后的编号
            int f_v = qry(p) + v - 1; // 树状数组中存的值是 f_i - i
            ans = min(ans, f_v + m - v);
            upd(p, f_v - v);
        }
    }
    wr(ans), pc('\n');
    return 0;
}