202012CSP认证#4. 食材运输

202012CSP认证#4. 食材运输

我太爬了… 一开始写个 $70$ 分做法都能把数组下标常量放错位置… 后面用真做法又是一边边界搞错… 一边连状态转移都能想复杂然后写错…

Solution

首先对于 $k=m$ 的情况, 也就是运输车之间互不干扰, 只要对于每一种情况求出最小花费的时间, 然后总的再取一个大的时间.

计算最小的时间: 对于每种食材, 可以发现其路径总是从某一个结点开始然后"转一圈"但是不需要再返回. 于是可以枚举每个点作为开始的结点(根节点), 然后利用树形dp获得以该节点为起点的花费, 然后对每个点取最小值. 用 $dp[u]$ 表示运输车当前在 $u$ 结点, 处理这棵子树需要花费的时间. 贪心地去做, 应该把带权深度最深的结点放到最后一个计算, 因为这个点计算后就没有必要再回到 $u$ 了.(这里和ccpc秦皇岛那个k有点类似). 所以复杂度是 $O(n)$ 的, 那么总的复杂度就是 $O(n^2k)$. 可以过 $70%$, 但是我不知道我哪里又爬了… 获得了 $65$…

很容易想到这应该是一道状态dp的题目, 考虑状态 $f[i][j][S]$ 表示在前面 $i$ 个结点中, 选取了 $j$ 个结点作为检查点, 并且覆盖了 $k$ 种食材的集合 $S$ 的最小时间代价. 那么如果添加一个新的结点 $i + 1$, 就考虑要不要作为新的检查点, 若不用, 就直接由 $f[i][j][S]$ 转移; 否则应该考虑 $i+1$ 去覆盖另一个子集, 然后将其与当前子集并起来再更新. 这样转移的复杂度是 $O(2^k)$ 的, 会 TLE. 但是可以发现, 如果第 $(i+1)$ 个点决定覆盖某一种食材, 那么那些花费时间比这个时间要小的食材也都会被覆盖, 因为在一段时间内允许并行. 所以实际上转移的子集只有 $O(k)$ 个. 时间复杂度: $O(nm2^{k}k)$.

Code

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
#define int long long
#define INF (1e14 + 7)

using namespace std;

struct Edge{
int to, nxt, w;
};

const int MAX_N = 1e2 + 7;
const int MAX_K = 17;
const int MAX_S = (1 << 10) + 7;
Edge e[MAX_N << 1];
int in[MAX_N][MAX_K], dp[MAX_N], head[MAX_N], mh[MAX_N], dep[MAX_N], son[MAX_N], ext[MAX_N], st[MAX_N][MAX_K], ti[MAX_N][MAX_K], f[MAX_N][MAX_K][MAX_S];
int cnt, now, n, m, k, ans;

void add(int u, int v, int w) {
e[++cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt; e[cnt].w = w;
}

void dfs(int u, int fa) {
ext[u] = in[u][now];
mh[u] = ext[u] ? dep[u] : 0;
son[u] = 0;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (v == fa) continue;
dep[v] = dep[u] + e[i].w;
dfs(v, u);
ext[u] = ext[u] | ext[v];
mh[u] = max(mh[u], mh[v]);
if (ext[v] && mh[son[u]] < mh[v]) son[u] = v;
}
}

void tree_dp(int u, int fa) {
int cost = 0, costs;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (v == son[u]) costs = e[i].w;
if (v == fa || v == son[u] || (!ext[v])) continue;
tree_dp(v, u);
dp[u] += cost + dp[v] + e[i].w;
cost = mh[v] - dep[u];
}
if (son[u]) tree_dp(son[u], u), dp[u] += cost + costs + dp[son[u]];
}

signed main() {
scanf("%lld%lld%lld", &n, &m, &k);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
scanf("%lld", &in[i][j]);
}
}
for (int i = 1; i < n; ++i) {
int u, v, w;
scanf("%lld%lld%lld", &u, &v, &w);
add(u, v, w); add(v, u, w);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
now = j;
memset(dp, 0, sizeof dp);
dep[i] = 0;
dfs(i, -1); tree_dp(i, -1);
ti[i][j] = dp[i];
}
for (int j = 1; j <= k; ++j) {
for (int t = 1; t <= k; ++t) {
if (ti[i][t] <= ti[i][j]) st[i][j] |= 1 << (t - 1);
}
}
}
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int s = 0; s < (1 << k); ++s) {
f[i][j][s] = INF;
}
}
}
for (int i = 0; i <= m; ++i) f[0][i][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int s = 0; s < (1 << k); ++s) {
for (int t = 1; t <= k; ++t) {
f[i + 1][j + 1][s | st[i + 1][t]] = min(max(f[i][j][s], ti[i + 1][t]), f[i + 1][j + 1][s | st[i + 1][t]]);
f[i + 1][j][s] = min(f[i + 1][j][s], f[i][j][s]);
}
}
}
}
printf("%lld\n", f[n][m][(1 << k) - 1]);
return 0;
}

評論

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×