A2780 | $对服务器场进行分区$

来源USACO / 2013

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

农民约翰的农场被划分为一个 N x N 方形的牧场网格（2 <= N <= 15）。现在，农场外面有围栏，但奶牛可以自由地从一个牧场移动到另一个牧场。 农场主约翰决定建造栅栏，将奶牛彼此隔开。由于分区法，每个围栏必须是横跨整个农场的水平线或垂直线，并且围栏不能穿过牧场。农夫约翰的钱最多只能建造 K 个栅栏（1 <= K <= 2N - 2）。 农场主约翰想建造围栏，以尽量减少最大的奶牛群的体型（如果两头奶牛可以在不穿过任何栅栏的情况下相互接触，则它们属于同一组）。鉴于每个牧场目前的奶牛数量，如果农民约翰以最佳方式建造围栏，请帮助农民约翰计算出最大奶牛群的大小。

* 第 1 行：两个整数，N 和 K * 第 2..1+N 行：每行有 N 个数字，描述农场一行每个牧场的奶牛（每个牧场至少有 0 头奶牛，最多 1000 头奶牛）

* 第 1 行：最大奶牛群的最小可能大小。

输入 #1

输出 #1

C++ 编辑器

输入

输出