问题 4830 --3.网格游走

4830: 3.网格游走

题目描述

  有一个由 $n$ 行 $m$ 列的 $1\times 1$  的格子组成的矩阵,每个格子 $(i,j)$  有对应的高度 $h_{i,j}$ 和初始的一个非负整数权值 $v_{i,j}$
你可以随便选择一个格子作为起点,然后在接下来的每一步当中,能且只能到达与当前格子有边相邻的四个格子中的高度不超过当前格子高度的格子,每当到达一个新格子(包括一开始选择的初始格子),就能将该格子的权值加入到你的得分中,然后该格子的权值就会等概率随机变成不比当前的权值大的一个非负权值。
每一个格子在满足条件的情况下,可以走任意多次。
我们希望得到一条路径,使得这个路径的期望总得分最大,请求出这个最大期望总得分。
请注意,这条路径可以是无限长的。

输入

第一行两个正整数 $n,m$,表示行数和列数。
接下来的 $n$ 行,每行 $m$ 个正整数,表示 $h_{i,j}$
接下来的 $n$ 行,每行 $m$ 个非负整数,表示 $v_{i,j}$

输出

一行一个实数,表示所求的最大期望得分,保留整数。

样例输入输出

输入#1 复制
1 3
1 2 1
1 2 3
输出#1 复制
5

提示

对于 $30\%$ 的数据,$ n,m \leq 100 $ ;
另外 $20\%$ 的数据,$h_{i,j}$互不相同;
对于 $70\%$ 的数据,$v_{i,j} \leq 10^6$;
对于 $100\%$ 的数据,$1\leq n,m \leq 1000 , 1 \leq h_{i,j} \leq 10^9, 0 \leq v_{i,j} \leq 10^9$。

序号 标题 作者 发表时间 费用 订购数 操作