[Kickstart Round C 2019 C. Catch Some] 动态规划

1. 题目链接

Kickstart Round C 2019 C. Catch Some

2. 题目描述

3. 解题思路

由题可知，除了最后一次需要走单程之外，其他每次都需要走双程（即需要回家)。

令 $dp_{(c,i,0)}$ 表示前 $c$ 种颜色，总共选出 $i$ 个人，并且前面 $c$ 种颜色 都是走的双程 的情况下的 最小花费时间；
$dp_{(c,i,1)}$ 表示前 $c$ 种颜色，总共选出 $i$ 个人，并且前面 $c$ 种颜色 存在一次走单程 的情况下的 最小花费时间。

记 $pos_{(c,i)}$ 表示第 $c$ 种颜色的狗中，距离家第 $i$ 近的狗的位置。

那么，可以写出状态转移方程如下：
$$
\begin{split}
dp_{(c,i+j,0)} &= \min \lbrace dp_{(c,j,0)} + 2 * pos_{(c,i)}\rbrace ;\
dp_{(c,i+j,1)} &= \min \lbrace dp_{(c,j,1)} + 2 * pos_{(c,i)},\ dp_{(c,j,0)} + pos_{(c,i)}\rbrace , \quad \text{for any } c,i,j.\
\end{split}
$$

因此， $ans=dp_{(M,K,1)}$。这里 $M$ 表示颜色种类数。

4. 参考代码

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

typedef long long ll;
typedef unsigned long long ull;

const int inf = 0x3f3f3f3f;

template<typename T> void umax(T& a, const T b) { a = max(a, b); }
template<typename T> void umin(T& a, const T b) { a = min(a, b); }

const int MAXN = 1005;
int T, K, N, A[MAXN], P[MAXN];
vector<int> dog_pos[MAXN];
int dp[MAXN][MAXN][2];

int main() {
#ifdef __LOCAL_WONZY__
    freopen("input-3.txt", "r", stdin);
#endif
    cin >> T;
    for(int cas = 1; cas <= T; ++cas) {
        cin >> N >> K;
        for(int i = 1; i < MAXN; ++i) dog_pos[i].clear();
        for(int i = 1; i <= N; ++i) cin >> P[i];
        for(int i = 1; i <= N; ++i) cin >> A[i];

        // re-indexed
        vector<int> buf(A+1, A+N+1);
        sort(buf.begin(), buf.end());
        buf.erase(unique(buf.begin(), buf.end()), buf.end());
        for(int i = 1; i <= N; ++i) {
            A[i] = lower_bound(buf.begin(), buf.end(), A[i]) - buf.begin() + 1;
        }
        int M = buf.size();

        for(int i = 1; i <= N; ++i) {
            assert(A[i] >= 1 && A[i] <= M);
            dog_pos[A[i]].push_back(P[i]);
        }

        for(int c = 1; c <= M; ++c) sort(dog_pos[c].begin(), dog_pos[c].end());
        memset(dp, 0x3f, sizeof(dp));
        dp[0][0][0] = 0;
        for(int c = 1; c <= M; ++c) {
            vector<int>& pos = dog_pos[c];
            for(int i = 0; i <= pos.size(); ++i) {
                for(int j = 0; i+j <= K; ++j) {
                    if(dp[c-1][j][0] == inf) break;
                    int dis = (i == 0) ? 0 : pos[i-1];
                    umin(dp[c][i+j][0], dp[c-1][j][0] + 2*dis);
                    umin(dp[c][i+j][1], min(dp[c-1][j][1] + 2*dis, dp[c-1][j][0] + dis));
                }
            }
        }
        printf("Case #%d: %d\n", cas, dp[M][K][1]);
    }
    return 0;
}