本题的正解为动态规划。
题意：题面讲的已经很清楚了，这里不做多解释。
思路：定义两个四维数组 f1f1 和 f2f2，f1_{x1,y1,x2,y2}f1x1,y1,x2,y2 表示左上角坐标为 (x1,y1)(x1,y1)，右下角坐标为 (x2,y2)(x2,y2) 的矩阵划分区域数的最大值，f2f2 记录在保证划分区域数最大的情况下能够剩余电力的最大值。定义变量 sumsum 表示电力需求总和 -− uu，我们需要保证划分后的任意一个区域的电力需求 \ge sum≥sum。
对于任意一个矩阵，我们只需要考虑它由哪两个矩阵转移过来（即横切和竖切），在转移的过程中，更新 f2f2 数组的值。
初始化：每枚举到一个矩阵，如果这个矩阵的权值 \ge sum≥sum（矩阵的权值即为矩阵中的所有数相加），就将 f1f1 初始化为 11，f2f2 赋值为这个矩阵的权值，这里的矩阵权值可以用前缀和实现。
实现步骤：
- 枚举矩阵 (x1,y1,x2,y2)(x1,y1,x2,y2)，如果这个矩阵满足权值和 \ge sum≥sum，初始化，否则跳出枚举下一个矩阵。
- 横切：kk 枚举矩阵的每一行，分割线在第 kk 行和第 k+1k+1 行之间，分割后的两个矩阵为 (x1,y1,k,y2)(x1,y1,k,y2) 和 (k+1,y1,x2,y2)(k+1,y1,x2,y2)，如果这两个矩阵的 f1f1 值都 \ge 1≥1，表示可以分割，更新 f1_{x1,y1,x2,y2}f1x1,y1,x2,y2 和 f2_{x1,y1,x2,y2}f2x1,y1,x2,y2 的值。代码如下：
if(f1[x1][y1][x2][y2]<f1[x1][y1][k][y2]+f1[k+1][y1][x2][y2]){ f1[x1][y1][x2][y2]=f1[x1][y1][k][y2]+f1[k+1][y1][x2][y2]; f2[x1][y1][x2][y2]=min(f2[x1][y1][k][y2],f2[k+1][y1][x2][y2]); } else if(f1[x1][y1][x2][y2]==f1[x1][y1][k][y2]+f1[k+1][y1][x2][y2]) f2[x1][y1][x2][y2]=max(f2[x1][y1][x2][y2],min(f2[x1][y1][k][y2],f2[k+1][y1][x2][y2])); - 竖切：思路和横切一样，把 kk 枚举行变为枚举列，分割后的两个矩阵变为 (x1,y1,x2,k)(x1,y1,x2,k) 和 (x1,k+1,x2,y2)(x1,k+1,x2,y2) 就好了。
时间复杂度：一共 55 层循环，时间复杂度为 O(n^5)O(n5)，对于 n \le 32n≤32 的数据是完全可以通过的。
code
#include<bits/stdc++.h>
using namespace std;
int n,m,u,sum=0;
int a[33][33];
int f1[33][33][33][33],f2[33][33][33][33],s[33][33];
int main(){
scanf("%d%d%d",&n,&m,&u);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
sum+=a[i][j];
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];//前缀和
}
sum-=u;
for(int len1=1;len1<=n;len1++)//前两层枚举矩阵的大小
for(int len2=1;len2<=m;len2++)
for(int x1=1,x2=x1+len1-1;x2<=n;x1++,x2++)//枚举矩阵左上角的坐标
for(int y1=1,y2=y1+len2-1;y2<=m;y1++,y2++){
int su=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
if(su<sum) continue;
f1[x1][y1][x2][y2]=1;
f2[x1][y1][x2][y2]=su-sum;//初始化
for(int k=x1;k<x2;k++){//横切
if(!(f1[x1][y1][k][y2]&&f1[k+1][y1][x2][y2])) continue;
if(f1[x1][y1][x2][y2]<f1[x1][y1][k][y2]+f1[k+1][y1][x2][y2]){
f1[x1][y1][x2][y2]=f1[x1][y1][k][y2]+f1[k+1][y1][x2][y2];
f2[x1][y1][x2][y2]=min(f2[x1][y1][k][y2],f2[k+1][y1][x2][y2]);
}
else if(f1[x1][y1][x2][y2]==f1[x1][y1][k][y2]+f1[k+1][y1][x2][y2])
f2[x1][y1][x2][y2]=max(f2[x1][y1][x2][y2],min(f2[x1][y1][k][y2],f2[k+1][y1][x2][y2]));
}
for(int k=y1;k<y2;k++){//竖切
if(!(f1[x1][y1][x2][k]&&f1[x1][k+1][x2][y2])) continue;
if(f1[x1][y1][x2][y2]<f1[x1][y1][x2][k]+f1[x1][k+1][x2][y2]){
f1[x1][y1][x2][y2]=f1[x1][y1][x2][k]+f1[x1][k+1][x2][y2];
f2[x1][y1][x2][y2]=min(f2[x1][y1][x2][k],f2[x1][k+1][x2][y2]);
}
else if(f1[x1][y1][x2][y2]==f1[x1][y1][x2][k]+f1[x1][k+1][x2][y2])
f2[x1][y1][x2][y2]=max(f2[x1][y1][x2][y2],min(f2[x1][y1][x2][k],f2[x1][k+1][x2][y2]));
}
}
printf("%d %d\n",f1[1][1][n][m],f2[1][1][n][m]);
return 0;
}
标签：x1,P2140,电力,33,矩阵,x2,管制,y1,y2 From： https://www.cnblogs.com/-111-/p/16884443.html