A22491.对服务器场进行分区
提高+/省选-
USACO
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
农民约翰的农场被划分为一个 N x N 方形的牧场网格(2 <= N <= 15)。现在,农场外面有围栏,但奶牛可以自由地从一个牧场移动到另一个牧场。
农场主约翰决定建造栅栏,将奶牛彼此隔开。由于分区法,每个围栏必须是横跨整个农场的水平线或垂直线,并且围栏不能穿过牧场。农夫约翰的钱最多只能建造 K 个栅栏(1 <= K <= 2N - 2)。
农场主约翰想建造围栏,以尽量减少最大的奶牛群的体型(如果两头奶牛可以在不穿过任何栅栏的情况下相互接触,则它们属于同一组)。鉴于每个牧场目前的奶牛数量,如果农民约翰以最佳方式建造围栏,请帮助农民约翰计算出最大奶牛群的大小。
输入格式
-
第 1 行:两个整数,N 和 K
-
第 2..1+N 行:每行有 N 个数字,描述农场一行每个牧场的奶牛(每个牧场至少有 0 头奶牛,最多 1000 头奶牛)
输出格式
- 第 1 行:最大奶牛群的最小可能大小。
输入输出样例
输入#1
3 2 1 1 2 1 1 2 2 2 4
输出#1
4
说明/提示
农民约翰应该在第 2 列和第 3 列之间以及第 2 排和第 3 排之间建造围栏,这样可以创建 4 组,每组有 4 头奶牛。