A2780. 对服务器场进行分区
编程题
提高+/省选-
知识点
题目描述
农民约翰的农场被划分为一个 N x N 方形的牧场网格（2 <= N <= 15）。现在，农场外面有围栏，但奶牛可以自由地从一个牧场移动到另一个牧场。
农场主约翰决定建造栅栏，将奶牛彼此隔开。由于分区法，每个围栏必须是横跨整个农场的水平线或垂直线，并且围栏不能穿过牧场。农夫约翰的钱最多只能建造 K 个栅栏（1 <= K <= 2N - 2）。
农场主约翰想建造围栏，以尽量减少最大的奶牛群的体型（如果两头奶牛可以在不穿过任何栅栏的情况下相互接触，则它们属于同一组）。鉴于每个牧场目前的奶牛数量，如果农民约翰以最佳方式建造围栏，请帮助农民约翰计算出最大奶牛群的大小。
农场主约翰决定建造栅栏，将奶牛彼此隔开。由于分区法，每个围栏必须是横跨整个农场的水平线或垂直线，并且围栏不能穿过牧场。农夫约翰的钱最多只能建造 K 个栅栏（1 <= K <= 2N - 2）。
农场主约翰想建造围栏，以尽量减少最大的奶牛群的体型（如果两头奶牛可以在不穿过任何栅栏的情况下相互接触，则它们属于同一组）。鉴于每个牧场目前的奶牛数量，如果农民约翰以最佳方式建造围栏，请帮助农民约翰计算出最大奶牛群的大小。
输入格式
* 第 1 行：两个整数，N 和 K
* 第 2..1+N 行：每行有 N 个数字，描述农场一行每个牧场的奶牛（每个牧场至少有 0 头奶牛，最多 1000 头奶牛）
* 第 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 头奶牛。