#P51296. 「CEOI2014」城墙

「CEOI2014」城墙

题目描述

译自 CEOI 2014 Day2 T3「The Wall」,原网站因为神秘原因没法访问了,这里用的 Web Archive 链接。

Rectos 岛经常遭受洪水的泛滥和海盗的侵扰,所以 Rectos 的国王想要建造一堵城墙以保护岛上所有的村庄。

Rectos 是一个矩形岛屿,所以城墙的设计师将岛屿看作一个正方形网格。每个村庄都位于其中的某个方格中,并且首都村庄位于整座岛的西北角,也就是最左上角的方格中。

必须保证从外部(也就是整个网格的外部)在不越过城墙的条件下,是到达不了任何一个村庄的。

设计师计划城墙将只沿着网格线建造,更具体地说是按照如下方法:他将第一段城墙置于最左上角延伸出的两条网格线之一上,并且下一段城墙总是和上一段城墙首尾相连,不断重复这一过程直到又一次回到最左上角为止。这一过程可能会导致一段网格线上放置了大于一段的城墙,总而言之,城墙是沿着网格线上的一条连续闭曲线建造的。

地势测量表明,在每一段网格线上建造一段城墙都需要一定的花费。建造城墙的总花费就是建造每一段城墙的花费之和。如果在某一段网格线上建造了 tt 段城墙,则花费也要重复计算 tt 次。

国王想要花费尽量少的钱建好城墙。请你帮助国王,编写一个程序,给出村庄的位置以及每一段网格线上的建造花费,计算建造城墙所需最小的花费。

输入格式

第一行两个正整数 n,mn, m,分别表示网格的行数和列数。
接下来 nn 行,每行 mm 个数,每个数为 0011,若为 00 则表示该格没有村庄,若为 11 则表示该格有村庄,保证第 11 行的第 11 个数一定为 11
接下来 nn 行,每行 m+1m + 1 个非负整数,依次表示每一段竖直的网格线上的建造花费。
接下来 n+1n + 1 行,每行 mm 个非负整数,依次表示每一段水平的网格线上的建造花费。

输出格式

输出一行一个数表示建造城墙的最小花费。

样例 1

3 3
1 0 0
1 0 0
0 0 1
1 4 9 4
1 6 6 6
1 2 2 9
1 1 1
4 4 4
2 4 2
6 6 6
38

pic1.png

3 3
1 0 1
0 0 0
0 1 0
2 1 1 3
5 6 1 1
2 1 1 3
2 1 1
3 4 1
4 1 1
5 1 2
22

pic2.png

数据范围与提示

对于所有数据,保证 1n,m4001 \le n, m \le 400,对于所有的建造花费 vv,有 1v1091 \le v \le {10}^9

子任务编号 分值 特殊限制
11 3030 n,m40n, m \le 40 且村庄的数量不超过 1010
22 n,m40n, m \le 40
33 4040 无特殊限制