P6158 封锁

震惊！zbw 竟从 B 城监狱逃出！ 作为 B 城的警察局长，你必须在 zbw 逃出你的管辖范围之前抓住他。

B 城可视为一个 $n \times n$ 的方阵，其中监狱在 $(1,1)$，B 城唯一出城的出口在 $(n,n)$。每两个相邻的点（横坐标之差的绝对值 $+$ 纵坐标之间的绝对值 $=1$）之间都有一条**无向的**道路（没有斜着的道路）。你需要在一些道路上部下防守，使得无论 zbw 怎么走，都至少会经过其中的一条道路。 在一条 $(i,j)$ 到 $(i,j+1)$ 的道路上部下防守的花费是 $r_{i,j}$，在一条 $(i,j)$ 到 $(i+1,j)$ 的道路上部下防守的花费是 $d_{i,j}$，同时，在道路上部下防守会对人民的生活造成影响，在一条 $(i,j)$ 到 $(i,j+1)$ 的道路上部下防守对人民的生活造成的影响是 $x_{i,j}$，在一条 $(i,j)$ 到 $(i+1,j)$ 的道路上部下防守对人民的生活造成的影响是 $y_{i,j}$。 定义总花费为 $w$ ，总影响为 $e$ ，作为一名优秀的警察局长，你需要最小化 $w \times e$。

无

无

 如图，左上角为 $(1,1)$，右下角为 $(n,n)$， 其中蓝色数字表示 $r$, 红色数字表示 $x$, 黄色数字表示 $d$, 绿色数字表示 $y$。 最优方案为防守三条边，分别为： $(2,2)-(2,3),(3,1)-(3,2),(3,2)-(3,3)$ 三条边的边权分别是 $2,3$---$1,1$ ---$4,3$ 答案为 $(1+2+4)\times (1+3+3)=49$ 可以发现没有更优的做法。 **本题采用捆绑测试。** | Subtasks| $n$ |特殊性质 |分数 | :----------: | :----------: | :----------: |:----------: | | Subtask1| $n=2$ |无 |$5$ | Subtask2| $n\leq400$ |数据随机 |$15$ | Subtask3| $n\leq10$ | 无|$15$ | Subtask4| $n\leq50$ | 无 |$30$ | Subtask5| $n\leq400$ | 无 |$35$ 对于所有数据 $1 \leq n \leq 400$，$0 \leq r_{i,j}, d_{i,j},x_{i,j} ,y_{i,j} \leq 10^3$。 数据于2020/3/4加强，卡掉部分复杂度错误的做法。