/ OIer TK / 题库 /

简单的网络游戏

简单的网络游戏

测试数据来自 system/1239

描述

在某款极具技术含量的网络游戏中,佳佳靠着他的聪明智慧垄断了游戏中的油田系统。

油田里有许多油井,这些油井排成一个M*N的矩形。每个油井都有一个固定的采油量。每两个相邻的油井之间有一条公路,这些公路是油井与油井之间唯一的运油方式。佳佳的领地在油田的右方和下方,他需要把采到的油通过这些公路运输到他的领地。为了保证采到的油以最快的方式供给右方和下方的领地,对于每个油井,佳佳总是将采到的油分成非空的两部分,将其中一部分沿公路一直向右运输到油田的右边界,将另一部分沿公路一直向下运输到油田的下边界。

然而树大招风,网络游戏中的GM以保证游戏公平为由,要求佳佳主动贡献出K个油井。更惨的是,失去某些油井不单意味着采油量减少,这还将会导致运输线路的中断。如果佳佳贡献出了某个油井,那么所有要经过这个油井的运输任务将无法完成。

佳佳想保证贡献K个油井之后自己的损失最小(损失即为失去的所有油井的采油量之和),而他希望其他的所有油井还能够像往常一样正常运输。于是他向你求救,希望你能帮助他实现他的想法。

格式

输入格式

第一行有三个用空格隔开的正整数M,N和K,它们分别表示油田的长、宽和佳佳需要贡献出的油田数。输入数据保证K<=M*N。

以下N行中每行有M个用空格隔开的正整数。这些正整数保证不超过10000,它们描述了油田中各个油井的采油量。

对于30%的数据,M<=10,N<=10;
对于100%的数据,M<=60,N<=60。

输出格式

一个整数,表示佳佳最少要损失的采油量。

样例1

样例输入1

5 3 4
3 4 1 4 5
1 10 7 8 13
3 5 8 9 11

样例输出1

9

限制

各测试点1秒

提示

样例说明:
佳佳贡献出下面标有“x”的油井是符合条件的最小损失方案。

x x x 4 5
x 10 7 8 13
3 5 8 9 11

来源

OIBH命题组原创 By matrix67

信息

ID
1230
难度
9
分类
动态规划 点击显示
标签
递交数
1
已通过
1
通过率
100%
上传者