2020-2021:teams:farmer_john:jjleo:codeforces_round_642_div._3
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:jjleo:codeforces_round_642_div._3 [2020/05/15 22:26] jjleo [E] |
2020-2021:teams:farmer_john:jjleo:codeforces_round_642_div._3 [2020/05/15 22:36] (当前版本) jjleo [F] |
||
|---|---|---|---|
| 行 19: | 行 19: | ||
| =====F===== | =====F===== | ||
| - | * 题意: | + | * 题意:给定一个$n \times m$的方格，每个格子有一个高度$a_{i,j}$，每次操作可以使得某个格子的高度减少$1$，高度可以减少到$0$或负数，要求存在一条路径从左上角到右下角，每次只能往下走或往右走，且只能往当前格子高度大$1$的格子移动，求最少操作次数。$(1 \le n, m \le 100, 1 \le a_{i, j} \le 10^{15})$ |
| - | * 题解: | + | * 题解:当左上角格子的高度确定后就可以直接dp判断是否有解和最小值，但$a_{i, j}$太大不能一个个枚举，注意到左上角格子之所以减少肯定是因为想到达某个格子，但是自己太高了以至于到那个格子后比那个格子的高度还高，所以最优取值一定是要么不减少、要么减少到可以恰好到某个格子的值，即$(a_{i,j}-i-j-2)$，因此暴力枚举然后分别dp即可，复杂度为$O(n^4)$。 |
2020-2021/teams/farmer_john/jjleo/codeforces_round_642_div._3.1589552773.txt.gz · 最后更改: 2020/05/15 22:26 由 jjleo
