[COCI 2014-2015 #7] ACM(ACM Task Assignment) 题解

思路分析

三名队员负责的三段连续非空任务一共有 $3! = 6$ 种先后排列顺序。枚举这 $6$ 种队员排列 $(p_0, p_1, p_2)$，对固定排列进行三阶段线性 DP（或记忆化搜索）：设 $f_0, f_1, f_2$ 分别表示处理到第 $i$ 题且当前处于第 $1, 2, 3$ 段时的最小难度和，每段至少包含 $1$ 道题，转移为 $f_2 \leftarrow \min(f_1, f_2) + d_{p_2, i}$，$f_1 \leftarrow \min(f_0, f_1) + d_{p_1, i}$，$f_0 \leftarrow f_0 + d_{p_0, i}$。取 $6$ 种排列的最小值即可，时间复杂度 $O(6n)$。

参考代码

#include <algorithm>
#include <iostream>
using namespace std;

const int MX = 150005;
int d[3][MX];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    for (int p = 0; p < 3; ++p)
        for (int i = 1; i <= n; ++i)
            cin >> d[p][i];

    const int INF = 1000000000;
    int perm[3] = {0, 1, 2};
    int ans = INF;
    do
    {
        int f0 = d[perm[0]][1], f1 = INF, f2 = INF;
        for (int i = 2; i <= n; ++i)
        {
            int nf2 = min(f1, f2);
            if (nf2 < INF) nf2 += d[perm[2]][i];
            int nf1 = min(f0, f1) + d[perm[1]][i];
            int nf0 = f0 + d[perm[0]][i];
            f0 = nf0;
            f1 = nf1;
            f2 = nf2;
        }
        ans = min(ans, f2);
    } while (next_permutation(perm, perm + 3));

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