CF 2003F Turtle and Three Sequences

首先分析一下这题的限制

p_i < p_{i + 1}, a_{p_i} < a_{p_{i + 1}}

和

b_{p_i} \not= b_{p_j}

。
相比之下，前两个限制更简单，因为其只限制于相邻的两数之间，而后一个限制要对所有

i, j

满足，只知道

b_{p_{i - 1}}

是不够的。

对于这种

\not =

的限制，一个想法是暴力钦定一些相同的情况（贝尔数）容斥，但因为这个题是最值相关，容斥在此也没有办法。
考虑这个限制为什么会很难处理，因为必须要知道前缀选的

b

的信息，但是这个状态数是

\binom{n}{m} + \binom{n}{m - 1} + \cdots + \binom{n}{0}

的，数量太过庞大所以不能直接用。

所以发现其实问题都出在这个

\binom{n}{m}

中的

n

，也就是

b

的种类数，本质上就是因为种类过多导致所需信息太多。
那一个想法就是考虑减少种类数使得所需的信息在可控的范围内。

于是可以考虑把

b

的值域限定在

[0, B)

这

B

个数中。
因为

b_i = b_j

肯定是不能被选在一起的，所以如果

b

的值相同被限定后的值也必须相同，所以这个限定就可以当作是从

b

的值域到

[0, B)

的映射。

但是又有问题，如何映射，又如何保证最优解会出现？
此时的一个做法是随机映射，考虑最优解的

m

个值，那么其

b

的映射的方案数为

B^m

；若该最优解可以表示出，那么这

m

个值对应的

b

的值就应该不同，对应方案数为

\binom{B}{m}\times m!

。
于是可以得到一个单次随机出最优解的概率：

\frac{\binom{B}{m}\times m!}{B^m}

。单次正确的概率可能不大，于是考虑多随几次，随机个

T

次，正确率就变为

1 - \bigg(1 - \frac{\binom{B}{m}\times m!}{B^m}\bigg)^T

（其实因为要求每个测试点都正确，所以通过的概率应该还需要有一个测试点的次方）。

接下来考虑把

b

的值域映射到了

[0, B)

后如何处理答案。
此时再考虑

p_i < p_{i + 1}, a_{p_i} < a_{p_{i + 1}}

的限制，考虑 DP，设计

f_{i, s}

表示考虑了

[1, i]

并且选的最后一个为

i

，

b

中选的集合为

s

的最大权值。
转移就直接考虑这些限制即可：

f_{i, s}\leftarrow f_{j, s - \{b_i\}} + c_i(j < i, a_j\le a_i, b_i\in s)

。
平衡这个查询和加入的复杂度，用一个树状数组优化即可。

最后时间复杂度

\mathcal{O}(T2^Bn\log n)

，正确率

1 - \bigg(1 - \frac{\binom{B}{m}\times m!}{B^m}\bigg)^T

，可以取

B = 7, T = 150

。

CPP

#include<bits/stdc++.h>
constexpr int maxn = 3e3 + 2, B = 7;
using arr = std::array<int, 1 << B>;
inline arr max(const arr &a, const arr &b) {
    arr c;
    for (int i = 0; i < (1 << B); i++) c[i] = std::max(a[i], b[i]);
    return c; 
}
int n, m;
arr tr[maxn];
inline void clear() {
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < (1 << B); j++) {
            tr[i][j] = j == 0 ? 0 : (int)-1e9;
        }
    }
}
inline void add(int x, const arr &y) {
    for (; x <= n; x += x & -x) tr[x] = max(tr[x], y);
}
inline arr query(int x) {
    arr y = tr[x];
    for (; x >= 1; x -= x & -x) y = max(y, tr[x]);
    return y;
}
std::mt19937_64 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
int a[maxn], b_[maxn], c[maxn];
int pb[maxn], b[maxn];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &b_[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
    int ans = -1;
    for (int t = 0; t < 150; t++) {
        for (int i = 1; i <= n; i++) pb[i] = rnd() % B;
        for (int i = 1; i <= n; i++) b[i] = pb[b_[i]];
        clear();
        for (int i = 1; i <= n; i++) {
            arr f = query(a[i]);
            for (int s = 0; s < (1 << B); s++) {
                if (~ s >> b[i] & 1) {
                    f[s | (1 << b[i])] = std::max(f[s | (1 << b[i])], f[s] + c[i]);
                }
            }
            add(a[i], f);
        }
        const arr f = query(n);
        for (int s = 0; s < (1 << B); s++) {
            if (__builtin_popcount(s) == m) {
                ans = std::max(ans, f[s]);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

CF 2003F Turtle and Three Sequences

文章操作

相关推荐

评论

CF 2003F Turtle and Three Sequences