目录：
一、前置知识
二、题目要求
三、解题思路
四、AC代码
前置知识：
????????本题解需要大家熟练掌握前缀和和二分算法的相关知识
题目要求：
? ? ? ? 把n*m的矩阵分成a*b块，求最小价值块的价值最大。
解题思路:
????????最大化最小点权之和，显然考虑二分答案。考虑二分一个值x，如何判断x是否能作为答案，也就是判断x是否能作为所有点的点权之和最小的一块小子矩阵的点权之和。等价于其他的所有小子矩阵的点权总和都要大于等于x。
????????记x为当前待检验的答案，t1当前水平方向切的条数，t2为当前竖直方向切的块数，k1为水平方向的上一次切割位置，k2为竖直方向的上一次切割位置。枚举水平方向上的切割点i和竖直方向上的切割点j，如果在(i?k1)～(j-k2)之间的点权之和大于等于x，那么符合要求，可以在这里切割，并更新各项信息。当t2≥b时就可以在i处切一条，t1++。最后只需判断t1≥a是否成立就等价于x是否能成为答案。
? ? ? ? 可能有些OIers不明白为什么t2≥b时就可以在i处切一条（或最后只需判断t1≥a是否成立即等价于x是否能成为答案），这里说明一下，t2记录的只是在哪个位置可以切割，而不是已经切割了多少次，所以只要大于或等于b即可（t1同理，记录的只是可以在那里切割，而不是已经切割了多少次，所以只要大于等于a即可）。
AC代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
#include<cstring>
using namespace std;
int n,m,a,b;
int sum[1001][1001];
int mapp[1001][1001];
bool check(int x)
{
int t1=0;//当前水平方向切的条数
int k1=0;//当前水平方向的上一次切割位置
for(int i=1;i<=n;i++)
{
int t2=0;//当前竖直方向切的块数
int k2=0;//竖直方向的上一次切割位置
for(int j=1;j<=m;j++)
{
if(sum[i][j]-sum[i][k2]-sum[k1][j]+sum[k1][k2]>=x)//计算当前分割后矩阵的值是否大于或等于x
{
t2++;
k2=j;
}
}
if(t2>=b)//如果t2>=b则符合条件
{
k1=i;
t1++;
}
}
return t1>=a;//如果t1>=a则返回1，否则返回0
}
int main()
{
scanf("%d%d%d%d",&n,&m,&a,&b);//基本的输入（个人喜欢用scanf()和printf()，就因为速度快）
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&mapp[i][j]);
}
}
for(int i=1;i<=n;i++)//二维前缀和预处理
{
for(int j=1;j<=m;j++)
{
sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+mapp[i][j];
}
}
int l=1;
int r=sum[n][m];
while(l+1<r)//二分查找
{
int mid=(l+r)>>1;
if(check(mid))
{
l=mid;
}
else
{
r=mid;
}
}
printf("%d\n",l);//基本的输出
return 0;
}?????????最后告诉大家一个秘密：?小编有在洛谷找到一样的题目哦：Brownie Slicing G
