CF1032C Playing Piano

· · 题解

题意简述

给定长度为 n 的序列 a，构造一个满足以下条件的 b，或者输出无解：

题目分析

构造方案如果不能以下想出来的话可以先考虑判断合法性。每一位 b_i 的取值都与上一位有关，且 b_i 的值域只有 5，因此考虑 DP。

设 dp_{i, j} = 1/0 表示第 i 位填 j 是否可行，由前一位转移，方程显然。

接下来考虑如何记录方案。只需要将每次选择的数据记录到 DP 数组里面就行。

改设 dp_{i, j} = s，其中 s \in [2 ^ 0, 2 ^ 4]，s 的第 k - 1 位为 1 表示可以从前一个 b_i 填 k 的情况转移过来；反之亦然。

状态转移方程：

dp_{i, j} = \begin{cases} \sum \limits _{k = 1} ^{j - 1} [dp_{i - 1, k} \neq 0] \times 2^k ,~ (a_i > a_{i - 1}) \\ \sum \limits _{k = j + 1} ^{5} [dp_{i - 1, k} \neq 0] \times 2^k ,~ (a_i < a_{i - 1}) \\ \sum \limits _{k = 1} ^{5} [j \neq k \land dp_{i - 1, k} \neq 0] \times 2^k ,~ (a_i = a_{i - 1}) \\ \end{cases}

最后 DFS 从后往前搜一遍统计路径即可。

时间复杂度 O(n)。

AC Code

CI N = 2e5 + 5;
int n, a[N], dp[N][6];
std::vector<int> v;
void dfs(int step, int finger) {
    if(step == 1) {
        std::reverse(all(v));
        for(int i : v) printk(i);
        exit(0);
    }
    rep(i, 1, 5) if((dp[step][finger] >> i - 1) & 1) v.p_b(i), dfs(step - 1, i), v.pop_back();
}
signed main() {
    n = read();
    arrin(a, n);
    rep(i, 1, 5) dp[1][i] = 1;
    rep(i, 2, n) rep(j, 1, 5)
        if(a[i] < a[i - 1]) rep(k, j + 1, 5) dp[i][j] |= !!dp[i - 1][k] << k - 1;
        else if(a[i] > a[i - 1]) rep(k, 1, j - 1) dp[i][j] |= !!dp[i - 1][k] << k - 1;
        else rep(k, 1, 5) if(k != j) dp[i][j] |= !!dp[i - 1][k] << k - 1;
    bool flag = 0;
    rep(i, 1, 5) flag |= dp[n][i];
    if(!flag) puts("-1"), exit(0);
    dp[n + 1][0] = -1;
    dfs(n + 1, 0);
    return 0;
}