题目链接：
- Mobile Service
题目思路：
- 这种题一看就是dp题，我们可以设f[i][j][k]为完成第i个命令时，第一个人在j位置，第二个人在k位置时最小花费，动动脑筋，我们不难推出
，
这道题的数据范围告诉我们，尽量要优化空间，相信大家都想到了， 要用滚动数组，对于状态i来说，状态只由i-1转移过来，这样我们可以把f[i][j][k],优化为f[i&1][j][k], i&1相当于i%2，只有1或0出现，这样就可以两者相互转化。代码
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
using namespace std;
int sc() {
int xx = 0, ff = 1; char cch = gc;
while(cch < '0' || cch > '9') {
if(cch == '-') ff = -1; cch = gc;
}
while(cch >= '0' && cch <= '9') {
xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
}
return xx * ff;
}
int l, n;
int c[Maxl][Maxl];
int p[Maxn];
int f[2][Maxl][Maxl];
int main() { // g++ "Mobile Service.cpp" -o "Mobile Service.exe" -Wall
l = sc(); n = sc();
for(int i = 1; i <= l; i++)
for(int j = 1; j <= l; j++)
c[i][j] = sc();
for(int i = 1; i <= n; i++)
p[i] = sc();
p[0] = 3;
memset(f, 0x7f, sizeof(f));
f[0][1][2] = 0;
for(int i = 1; i <= n; i++) {
for(int x = 1; x <= l; x++) {
for(int y = 1; y <= l; y++) {
if(f[i - 1 & 1][x][y] != Maxx) {
int z = p[i - 1];
if(x != p[i] && y != p[i])
f[i & 1][x][y] = min(f[i & 1][x][y], f[i - 1 & 1][x][y] + c[z][p[i]]);
if(y != p[i] && z != p[i])
f[i & 1][z][y] = min(f[i & 1][z][y], f[i - 1 & 1][x][y] + c[x][p[i]]);
if(x != p[i] && z != p[i])
f[i & 1][x][z] = min(f[i & 1][x][z], f[i - 1 & 1][x][y] + c[y][p[i]]);
f[i - 1 & 1][x][y] = Maxx;
}
}
}
}
int ans = 0x7fffffff;
for(int i = 1; i <= l; i++)
for(int j = 1; j <= l; j++)
ans = min(ans, f[n & 1][i][j]);
printf("%d\n", ans);
return 0;
}
rp++