基本思路：二分答案；
(代码繁琐，勿怪)
解析：想到二分答案后，繁琐的地方在于如何确定一个答案是否可行，要注意，纵切一刀不意味着这一列的蛋糕都为同个形状，而是只切分好的这一行，分好的行之间互不影响。
我们用贪心的原理去计算这一行的蛋糕，一旦他大于等于（所有的蛋糕都一定大于等于枚举值）枚举值，就可以算切了两列(totl)（这样后面就能得到更多的蛋糕）(需要totl>=c)，如果这行满足不了纵切那么多刀，就再加上一行，再去计算，直到可以满足（toth>=r），就算作切了一行（toth）再换成下一行。最后看看是否满足切需要的行数，若满足这个答案就是成立的！
#include<iostream> #include<cstdio> using namespace std; int lef,righ,mid,sum,r,c,x,y,ans,b[1000][1000],a[1000][1000]; bool f; bool check(int k) { int lasth,nowl,lastl,nowh,sum,totl,toth; lasth=0;//上次的行号 lastl=0;//上次的列号 nowh=1;//现在的行号 f=false;//表示现在切得这行是否满足枚举的值； toth=0; while (nowh<=r) { sum=0; lastl=0; f=false; nowl=0; totl=0; while (nowl<c) { ++nowl;//枚举列号 sum=b[nowh][nowl]-b[lasth][nowl]-b[nowh][lastl]+b[lasth][lastl];//当前枚举的区域的值 if (sum>=k)//如果分的蛋糕的值大于等于枚举的值 { totl+=1;//表示这条蛋糕已经分了几列 if (totl>=y)//如果可分的列数已经大于等于需分的列数 { f=true;//那么这块蛋糕一定符合枚举条件及这条蛋糕可以这样分 break; } sum=0; lastl=nowl; //更新列号，去枚举这行上的下块符合条件的蛋糕 } } if (f==true)//如果这行成立的话 { lasth=nowh;//换一行 toth+=1;//y可分的行数+1 } if ((toth>=x)&&(f==true)) return true;//如果已分的行数已达到所需行数且现在枚举的这行符合条件（这要这行符合下面的可以累加在它的上面，一定成立），那么这个枚举是可以的。 if ((f==false)&&(nowh==r)) return false;//如果这行不成立且已经是最后一行了，那么这个答案不可以！ nowh+=1;//加上一行去试试是否成立 } if (toth<x) return false;//如果已是最后一行却依然没分够所需的行数，那么也是不成立的 } int main() { cin>>r>>c>>x>>y; sum=0; for (int i=1;i<=r;++i) for (int j=1;j<=c;++j) { cin>>a[i][j]; sum+=a[i][j]; b[i][j]=a[i][j]; } for (int i=1;i<=r;++i) for (int j=1;j<=c;++j) b[i][j]=b[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1]; //为了计算方便写矩阵前缀和，可忽略 lef=0; righ=sum/(x*y)+2;最多能拿到多少，+2是随便加的，以防万一 ans=0; while (lef<=righ) { mid=(lef+righ)/2; if (check(mid)==true) { lef=mid+1; if (mid>ans) ans=mid; } else righ=mid-1; } cout<<ans<<endl; return 0; }