Problem F: 邻家割草
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$363$ |
正确数量 |
$113$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
|
当前分类(单击移除)：
单击选择分类：
邻居Alice家有一块大草坪，每隔一段时间他都要用割草机修剪草坪;可以把草
坪看成是一个N*M的矩阵，割草时需要N台割草机水平方向穿过草地，M台
割草机垂直方向穿过草地。草地并不是完全平整的，有高有低;如图所示，高的
地方用深色表示，矮的地方用浅色表示，
割草机工作时需要消耗燃油，在走过不同高度的草地时，会消耗A元燃油燃油
费; (比如从低的地方走到高的地方，从高的地方走到低的地方，在相同高度的
地块上运行割草机的燃油消耗可以忽略)。Alice为了节省燃油费，准备改造-.
些地形;可以给一些地块加土来升高地形,或者把高的地方铲平来降低地形高度.
对一个地块进行改造要花费B元。你能帮邻居Alice 设计一个方案。让他花费最
小吗?
输人
输人的第一行是四个整数NMAB,分别表示矩阵有N行，M列;走过不同高
度的地块需要多花费A元;调整地块高度需要花费B元.
接下来N行，每行M个字符，描述来草坪地形。'#代表高的地块， 字符:代表
低的地块。
1 <=N,M<= 50
输出 Alice 改造地块 + 割草的最小花费
5 4 1000 2000
. . . #
# . . #
. . . #
# # . .
# # # .
Alice的草地大小是5x4,在不同高度的地块上行走每个割草机要多花费1000
元，调整一个地块的地形需要花费2000元;
Alice最少需要11000元: 2000 元用于修改第二行第一个地块，把这个地块的
高度降低。9000 元用于割草，水平方向运行的5台割草机花费5000元，垂直
方向运行的4台割草机花费4000元。