Luogu P4046 [JSOI2010]快递服务

题目链接

这个题的输入挺坑的。。。反正我调了挺久。

$f_{i,j,k,l}$表示到第$i$个取货位置,三个车的位置分别在$i,j,k$,那么转移可以是:
$$
f_{i,j,k,a_i}=min(f_{i,j,k,a_i},f_{i,j,k}+dis(l,a_i))
$$
$$
f_{i,j,a_i,l}=min(f_{i,j,a_i,l},f_{i,j,k}+dis(k,a_i))
$$
$$
f_{i,a_i,k,l}=min(f_{i,a_i,k,l},f_{i,j,k}+dis(j,a_i))
$$
这样枚举一下$i,j,k$,取最小值即为答案。

然后时间空间就都炸了。。。

考虑优化:
因为肯定有一个车的位置在$a_{i-1}$这样可以省去一维,然后第一维做一个滚动数组。
$$
f_{i,j,k}=min(f_{i,j,k},f_{i-1,j,k}+dis(a_{i-1},a_i))
$$
$$
f_{i,j,a_{i-1}}=min(f_{i,j,a_{i-1}},f_{i-1,j,k}+dis(k,a_i))
$$
$$
f_{i,a_{i-1},k}=min(f_{i,a_{i-1},k},f_{i-1,j,k}+dis(j,a_i))
$$
这个得仔细思考一下才行,我看题解的时候这里一直理解不了,之所以是转移到$a_{i-1}$而不是$a_i$是可以通过原来的那个没有优化的想一想得到的。。。反正玄学。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;

int n, m;
ll d[209][209];
ll f[2][209][209];
int a[1009];

int main(){
scanf("%d", &m);
for(int i = 1; i <= m; i++){
for(int j = 1; j <= m; j++){
scanf("%d", &d[i][j]);
f[0][i][j] = f[1][i][j] = inf;
}
}
int n = 1;
while(scanf("%d", &a[n]) == 1) n++;
n--;
int now = 0, last = 1;
f[0][1][2] = 0;
a[0] = 3;
for(int t = 1; t <= n; t++){
now = 1-now, last = 1-last;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= m; j++){
f[now][i][j] = inf;
}
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= m; j++){
if(i == j || j == a[t-1] || i == a[t-1]) continue;
if(f[last][i][j] == inf) continue;
if(i != a[t] && j != a[t])
f[now][i][j] = min(f[now][i][j],f[last][i][j]+d[a[t-1]][a[t]]);
if(j != a[t])
f[now][a[t-1]][j] = min(f[now][a[t-1]][j],f[last][i][j]+d[i][a[t]]);
if(i != a[t])
f[now][i][a[t-1]] = min(f[now][i][a[t-1]],f[last][i][j]+d[j][a[t]]);
}
}
}
ll ans = inf;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= m; j++){
ans = min(ans, f[now][i][j]);
}
}
printf("%d\n", ans);
return 0;
}
# dp

评论

Your browser is out-of-date!

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

×