题目名称 2956. 分割之美
输入输出 Lovelove_boii_divide.in/out
难度等级 ★☆
时间限制 1000 ms (1 s)
内存限制 256 MB
测试数据 10 简单对比
题目来源 2018-07-07
开放分组 全部用户
提交状态
分类标签
通过:1, 提交:1, 通过率:100%
Gravatar梦那边的美好ETMN 100 0.161 s C++
关于 分割之美 的讨论

2956. 分割之美

★☆   输入文件:Lovelove_boii_divide.in   输出文件:Lovelove_boii_divide.out   简单对比
时间限制:1 s   内存限制:256 MB

【题目描述】


今天Lovelove_boii在追求分割之美。

Lovelove_boii正在分割自己手中的一个矩阵,这个矩阵有n行m列,Lovelove_boii想知道如何分割这个矩阵才美,因此他定义了一种“美分割”。 将矩阵分割成a*b块,先水平分割a-1次(只沿整数坐标切分)将矩阵分为a块,然后将每一块独立的分割b-1次(只沿整数坐标切分),对于所有分割方案,其中最小的子矩阵中所有节点的和最大的方案为“美分割”。



【输入格式】


第一行四个正整数n,m,a,b

接下来n行每行m个数 表示Lovelove_boii要分割的矩阵


【输出格式】

输出一个整数,表示“美分割”中所有子矩阵中节点和最小的子矩阵和

【样例输入】

5 4 4 2

1 2 2 1

3 1 1 1

2 0 1 3

1 1 1 1

1 1 1 1

【样例输出】

3

【提示】


对于20%的数据,满足a,b≤ n,m ≤ 10  b=1

对于50%的数据,满足a,b≤ n,m ≤ 50  b=2

对于60%的数据,满足a,b≤ n,m ≤ 100

对于100%的数据,满足1≤ a,b≤ n,m ≤ 500  1≤ a,b≤500  0≤所有点值≤50



【来源】

在此键入。