CF1621 D.The Winter Hike【贪心】

题目链接：codeforces 1621D

题解

不难得出右下角的所有雪全清，接下来就是找到右上角到右下角的路径。关键是找到到右下角区域的入口。根据移动方式，再贪心只选择一个入口，画图可知只有八个入口，取最小值即可。

image-20220108193401839

参考代码

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
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 550;
int n;
ll a[maxn][maxn];
void solver() {
	ll ans = 0;
    cin >> n;
    for (int i = 1; i <= n * 2; i++) {
        for (int j = 1; j <= n * 2; j++) {
            cin >> a[i][j];
            if (i >= n+1 && j >= n+1) {
                ans += a[i][j];
            }
        }
    }
    ll oth = min(a[1][n+1], min(a[1][2*n], min(a[n][n+1], min(a[n][2*n], min(a[n+1][1], min(a[n+1][n], min(a[2*n][1], a[2*n][n])))))));
    ans += oth;
    cout << ans << '\n';
}
int main() {
    int _ = 1;
    cin >> _;
    while (_--) {
        solver();
    }
}