红牌 - 题目列表

题意

有 m 个小组，要完成 n 个步骤。

第 i 组做第 j 步需要 cost[i][j] 天。

每一步你可以：

继续留在当前组；
或在相邻两步之间切换到下一组（m 的下一组视作 1）。

要求求出完成全部步骤的最小总代价。

思路

最直接的教学版做法是搜索每一步“留在本组”还是“切到下一组”：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50// brute.cpp：搜索所有“留在本组/切到下一组”的方案，作为教学版和对拍基准程序。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;
const long long INF = (1LL << 60);

int n, m;
int cost_days[MAXN][MAXN];
long long ans = INF;

int next_group(int x) {
    if (x == m) {
        return 1;
    }
    return x + 1;
}

void dfs(int step, int group, long long sum) {
    if (sum >= ans) {
        return;
    }
    if (step == n) {
        ans = min(ans, sum);
        return;
    }

    dfs(step + 1, group, sum + cost_days[group][step + 1]);
    int ng = next_group(group);
    dfs(step + 1, ng, sum + cost_days[ng][step + 1]);
}

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

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> cost_days[i][j];
        }
    }

    for (int start = 1; start <= m; start++) {
        dfs(1, start, cost_days[start][1]);
    }

    cout << ans << '\n';
    return 0;
}

但正式解法用 DP 更自然。

设 dp[i] 表示当前处理到某一步时，停在第 i 组的最小总代价。

如果这一列要到第 i 组，那么上一列只能来自：

原本就在第 i 组；
原本在第 i 的前一个组，然后本步切换过来。

所以转移是：

new_dp[i] = min(dp[i], dp[prev(i)]) + cost[i][step]

第一步可以任选小组，因此直接初始化为第一列代价。

DP 公式

设 $dp_i$ 表示处理完当前步骤后停在第 $i$ 组的最小总代价。第一步初始化为：

dp_i=cost_{i,1}

第 $step$ 步的转移是：

new\_dp_i=\min(dp_i,\ dp_{prev(i)})+cost_{i,step}

其中：

prev(i)=\begin{cases} m, & i=1,\\ i-1, & i>1. \end{cases}

最终答案为：

\min_{1\leqslant i\leqslant m} dp_i

公式解释：第 step 步停在第 i 组时，上一刻只能已经在第 i 组，或者从环上的前一组转过来。两者取较小值后再加上当前组完成这一步的代价，就得到新的最小总代价。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2005;
const long long INF = (1LL << 60);

int n, m;
int cost_days[MAXN][MAXN]; // cost_days[i][j]：第 i 组做第 j 步所需天数
long long dp[MAXN];        // 当前处理到某一步时，dp[i] 表示在第 i 组的最小代价
long long ndp[MAXN];

int prev_group(int x) {
    if (x == 1) {
        return m;
    }
    return x - 1;
}

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

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> cost_days[i][j];
        }
    }

    for (int i = 1; i <= m; i++) {
        dp[i] = cost_days[i][1];
    }

    for (int step = 2; step <= n; step++) {
        for (int group = 1; group <= m; group++) {
            ndp[group] = min(dp[group], dp[prev_group(group)]) + cost_days[group][step];
        }
        for (int group = 1; group <= m; group++) {
            dp[group] = ndp[group];
        }
    }

    long long ans = INF;
    for (int i = 1; i <= m; i++) {
        ans = min(ans, dp[i]);
    }

    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度： $O(nm)$
空间复杂度： $O(m)$

总结

这题的本质是一个很标准的“按列推进”的阶段型 DP。

关键只在于看清楚：每个状态的来源永远只有两个。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

红牌

目录

题意

思路

DP 公式

代码

复杂度

总结

一图流解析