马拉松接力赛(Marathon Relay) 题解

思路分析

每名队员至少跑 $1\text{ km}$，先给 $5$ 名队员各分配 $1\text{ km}$（共 $5\text{ km}$）。由于每名队员连续跑的速度不会变快（即多跑 $1\text{ km}$ 的边际耗时 $t_{i, k+1} - t_{i, k}$ 单调不降），接下来剩余的 $20\text{ km}$ 每次贪心选择当前未满 $10\text{ km}$ 且「多跑 $1\text{ km}$ 边际增加耗时最小」的队员增加 $1\text{ km}$ 即可（或直接做 $5$ 人背包 DP 求全局最优并回溯方案）。

参考代码

#include <iostream>
using namespace std;

long long t[6][11];
long long dp[6][26];
int preKm[6][26];
int ansKm[6];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 1; i <= 5; ++i)
    {
        for (int j = 1; j <= 10; ++j)
        {
            if (!(cin >> t[i][j])) return 0;
        }
    }
    const long long INF = (1LL << 60);
    for (int i = 0; i <= 5; ++i)
        for (int s = 0; s <= 25; ++s)
            dp[i][s] = INF;
    dp[0][0] = 0;
    for (int i = 1; i <= 5; ++i)
    {
        for (int s = i; s <= 25; ++s)
        {
            for (int k = 1; k <= 10 && k <= s; ++k)
            {
                if (dp[i - 1][s - k] + t[i][k] < dp[i][s])
                {
                    dp[i][s] = dp[i - 1][s - k] + t[i][k];
                    preKm[i][s] = k;
                }
            }
        }
    }
    cout << dp[5][25] << "\n";
    int cur = 25;
    for (int i = 5; i >= 1; --i)
    {
        ansKm[i] = preKm[i][cur];
        cur -= ansKm[i];
    }
    for (int i = 1; i <= 5; ++i)
    {
        if (i > 1) cout << " ";
        cout << ansKm[i];
    }
    cout << "\n";
    return 0;
}