道路

Posted on In

题目大意: 我们看见了一个由m行n列的1*1的格子组成的矩阵，每个格子(i,j)有对应的高度h[i][j]和初始的一个非负权值v[i][j]。我们可以随便选择一个格子作为起点，然后在接下来的每一步当中，我们能且只能到达与当前格子有边相邻的四个格子中的高度不超过当前格子高度的格子，每当我们到达一个新格子（包括一开始选择的初始格子），我们就能得到该格子的权值分，然后该格子的权值就会等概率变成不比当前的权值大的一个非负权值。每一个格子在满足前面条件情况下，可以走任意多次。我们希望得到一个最大的期望权值和路径，并给出这个最大的期望权值和。

这题说白了就是选定一个点，然后不定走走走，但是有个特殊的地方就是这个点走过一次之后的权值会等概率的变成不大于当前权值的一个数字

来自一位大佬的话,每一次取完之后如果可以回来的话取值范围:[0,v_i],平均期望就是0.5v_i

所以\(v_i+0.5v_i+0.25v_i + ...->2v_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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;

const int N = 1e3 + 66;
const int dirx[5] = {-1, 1, 0, 0};
const int diry[5] = {0, 0, -1, 1};

int n, m, res, sum;
int h[N][N], v[N][N], bel[N][N];
vector<int>e[N * N];
int f[N * N], val[N * N], lix[N * N], liy[N * N];

inline void bfs(int tx, int ty)
{
    int l(1), r(1), x, y, nx, ny, i;
    lix[1] = tx, liy[1] = ty, val[sum] = v[tx][ty], bel[tx][ty] = sum;
    for (; l <= r; ++ l)
    {
        x = lix[l], y = liy[l];
        for (i = 0; i < 4; ++ i)
        {
            nx = x + dirx[i], ny = y + diry[i];
            if (! nx || nx > m || ! ny || ny > n || h[nx][ny] != h[x][y] || bel[nx][ny]) continue;
            lix[++ r] = nx, liy[r] = ny;
            val[sum] += v[nx][ny];
            bel[nx][ny] = sum;
        }
    }
    if (r > 1) val[sum] *= 2;
    return;
}

inline int func(int x)
{
    if (f[x] != -1) return f[x];
    f[x] = 0;
    for (int j = 0; j < (int)e[x].size(); ++ j) f[x] = max(f[x], func(e[x][j]));
    f[x] += val[x];
    return f[x];
}

signed main()
{	
    int i, j, x, y;
    m = read(), n = read(), memset(f, -1, sizeof f);
    for (i = 1; i <= m; ++ i) for (j = 1; j <= n; ++ j) h[i][j] = read();
    for (i = 1; i <= m; ++ i) for (j = 1; j <= n; ++ j) v[i][j] = read();

    for (i = 1; i <= m; ++ i) for (j = 1; j <= n; ++ j) if (! bel[i][j]) ++ sum, bfs(i, j);

    for (x = 1; x <= m; ++ x)
    {
        for (y = 1; y <= n; ++ y)
        {
            for (i = 0; i < 4; ++ i)
            {
                int nx = x + dirx[i], ny = y + diry[i];
                if (! nx || nx > m || ! ny || ny > n || h[nx][ny] >= h[x][y]) continue;
                e[bel[x][y]].push_back(bel[nx][ny]);
            }
        }
    }

    for (i = 1; i <= sum; ++ i) res = max(res, func(i));
    put(res);

    return 0;
}