[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$ 近的狗的位置。

那么,可以写出状态转移方程如下:

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

4. 参考代码

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
51
52
53
54
55
56
57
58
59
#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;
}
坚持原创技术分享,您的支持将鼓励我继续创作!