本题的正解为动态规划。

题意：题面讲的已经很清楚了，这里不做多解释。

思路：定义两个四维数组 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 赋值为这个矩阵的权值，这里的矩阵权值可以用前缀和实现。

实现步骤：

  1. 枚举矩阵 (x1,y1,x2,y2)(x1,y1,x2,y2)，如果这个矩阵满足权值和 \ge sum≥sum，初始化，否则跳出枚举下一个矩阵。
  2. 横切：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]));
  3. 竖切：思路和横切一样，把 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;
}

　　

原文地址：http://www.cnblogs.com/-111-/p/16884443.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性