Codeforces 2195C 题解：Dice Roll Sequence（线性 DP）

题目链接：https://codeforces.com/contest/2195/problem/C

题意重述

给一个长度为 n 的序列 a（每个值在 1..6）。
相邻两项必须满足：

• 不能相等
• 不能互为对面（即 x + y != 7）

一次操作可以把任意位置改成 1..6 中任意值。
问最少改多少次，才能让整个序列合法。

思路

把“改值次数最少”做成位置 DP。

设 dp[i][v] 表示：

• 前 i 个位置（0..i）已经处理完
• 第 i 个位置最终取值是 v
• 所需最少修改次数

转移：

如果 u -> v 合法（u != v 且 u + v != 7），则

dp[i][v] = min(dp[i][v], dp[i-1][u] + (a[i] != v))

初始：

dp[0][v] = (a[0] != v)

答案：

min(dp[n-1][1..6])

因为状态只有 6 个，复杂度很小：

• 时间复杂度 O(n * 6 * 6)
• 空间复杂度 O(6)（滚动数组）

C++17 代码

#include <bits/stdc++.h>
using namespace std;

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];

        const int INF = 1e9;
        array<int, 7> dp{}, ndp{};

        for (int v = 1; v <= 6; ++v) {
            dp[v] = (a[0] == v ? 0 : 1);
        }

        for (int i = 1; i < n; ++i) {
            for (int v = 1; v <= 6; ++v) ndp[v] = INF;

            for (int v = 1; v <= 6; ++v) {
                int cost = (a[i] == v ? 0 : 1);
                for (int u = 1; u <= 6; ++u) {
                    if (u == v) continue;
                    if (u + v == 7) continue;
                    ndp[v] = min(ndp[v], dp[u] + cost);
                }
            }

            dp = ndp;
        }

        int ans = INF;
        for (int v = 1; v <= 6; ++v) ans = min(ans, dp[v]);
        cout << ans << '\n';
    }

    return 0;
}

样例解释

• 1 4 2 本来就满足条件，答案 0。
• 3 4 6 3 中 4 和 6 互为对面，改一次即可，答案 1。

易错点

1. 合法条件是同时满足：u != v 且 u + v != 7。
2. 改值可以改成任意 1..6，不是只能在原值附近调整。
3. n=1 时没有相邻限制，答案始终是 0（DP 也会自然得到这个结果）。