题目描述
https://codeforces.com/contest/1421/problem/D
Solution
首先肯定要分象限考虑
注意到向右上走的价值可能并不优于先向右在向上
其它六个方向同理，所以我们先更新一波向每个方向走的最优值
然后对于每个象限，能斜着走就斜着走
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
int n, x, y;
ll c[7];
ll ans;
void work() {
cin >> x >> y;
for (int i = 1; i <= 6; ++i) cin >> c[i];
c[1] = min(c[1], c[2] + c[6]);
c[2] = min(c[2], c[1] + c[3]);
c[3] = min(c[3], c[4] + c[2]);
c[4] = min(c[4], c[3] + c[5]);
c[5] = min(c[5], c[4] + c[6]);
c[6] = min(c[6], c[1] + c[5]);
if (x >= 0 && y >= 0) {
if (x > y) ans = (x - y) * c[6] + y * c[1];
else ans = (y - x) * c[2] + x * c[1];
}
else if (x <= 0 && y <= 0) {
x = abs(x); y = abs(y);
if (x > y) ans = (x - y) * c[3] + y * c[4];
else ans = (y - x) * c[5] + x * c[4];
}
else if (x >= 0) {
y = abs(y);
ans = y * c[5] + x * c[6];
}
else {
x = abs(x);
ans = x * c[3] + y * c[2];
}
cout << ans << endl;
}
int main() {
int T; cin >> T;
while (T--) work();
return 0;
}
|