Boggle Sort 的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

考虑 DP，令 \(dp(x)\) 表示处理到当前骰子，且序列最后一个字符为 \(x\) 时的最小转动次数。

对于第 \(i\) 个骰子，枚举它的 \(6\) 个面。假设转动到某个面（该面字符为 \(x\)）需要的代价为 \(c\)，为了满足字典序非降序的要求，第 \(i - 1\) 个骰子结尾字符 \(y\) 必须满足 \(y \le x\)，状态转移方程写为： \[ ndp(x) = \min_{y \le x}dp(y) + c \] 预处理前缀最小值和滚动数组优化，时间复杂度 \(O(1)\)。

#include <bits/stdc++.h>

using i64 = long long;

using real = long double;

constexpr int inf = 1E8;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::vector<std::string> s(6);
    for (int i = 0; i < 6; i++) {
        std::cin >> s[i];
    }

    std::vector<int> dp(26, inf);
    std::vector<int> cost{0, 1, 1, 1, 1, 2};
    for (int i = 0; i < 6; i++) {
        int x = s[i][0] - 'A';
        dp[x] = std::min(dp[x], cost[i]);
    }

    for (int i = 1; i < 16; i++) {
        std::vector<int> minv(26, inf);
        for (int y = 0; y < 26; y++) {
            int ny = (y == 'Q' - 'A' ? 'U' - 'A' : y);
            minv[ny] = std::min(minv[ny], dp[y]);
        }
        for (int y = 1; y < 26; y++) {
            minv[y] = std::min(minv[y], minv[y - 1]);
        }

        std::vector<int> ndp(26, inf);
        for (int j = 0; j < 6; j++) {
            int x = s[j][i] - 'A';
            ndp[x] = std::min(ndp[x], minv[x] + cost[j]);
        }
        dp = std::move(ndp);
    }

    int ans = *std::min_element(dp.begin(), dp.end());
    if (ans == inf) {
        std::cout << "impossible\n";
    } else {
        std::cout << ans << "\n";
    }


    return 0;
}

目前没有评论。