题意：给定一个长方形网格，要把它切成完全相同4个部分（这里完全相同指可以旋转平移后能重叠）。把4个重叠后每个网格对应有四个数字相加，得到一种方案，所有格子中和最小就是该种方案的值，在多种方案中，最后问最大的解能使多少。

思路：首先任意一种划分可以映射到4个相同的长方形， 也就是说一种不是长方形的方案 可以转化为一种长方形的。那么我们就只需要找4个完全相同的长方形就可以。一共有以下画法：

下面画图时基于n>m。边长要满足一定条件要自己注意。

#include <iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define debug(x) printf(#x"= %d\n",x);

using namespace std;

struct node {

    int a[][];

    int n, m;

    void rota() {//旋转90度

        int b[][];

        for (int i = ; i < n; ++i) {

            for (int j = ; j < m; ++j) {

                b[j][n - i - ] = a[i][j];

            }

        }

        swap(n, m);

        for (int i = ; i < n; ++i)

            for (int j = ; j < m; ++j)

                a[i][j] = b[i][j];

    }

} p[], s;

int a[][];

int n, m;

int ans;

node cur[];

void gao(int now) {

    if (now == ) {

        for (int i = ; i < ; ++i)

            if (cur[i].n != cur[i + ].n || cur[i].m != cur[i + ].m)

                return;

        int minn = ;

        for (int i = ; i < cur[].n; ++i) {

            for (int j = ; j < cur[].m; ++j) {

                int sum = ;

                for (int k = ; k < ; ++k) {

                    sum += cur[k].a[i][j];

                }

                //    printf("%d %d %d\n",i,j,sum);

                if (sum < minn)

                    minn = sum;

            }

        }

        if (minn > ans)

            ans = minn;

        return;

    }

    cur[now] = p[now];

    gao(now + );

    for (int i = ; i < ; ++i) {

        cur[now].rota();

        gao(now + );

    }

}

int main() {

    while (scanf("%d%d", &n, &m) != EOF) {

        for (int i = ; i < n; ++i)

            for (int j = ; j < m; ++j)

                scanf("%d", &a[i][j]);

        //debug(m);

        ans = ;

        if (n %  == ) {

            for (int i = ; i < ; ++i) {

                for (int j = n /  * i; j < n /  * (i + ); ++j) {

                    for (int k = ; k < m; ++k) {

                        p[i].a[j % (n / )][k] = a[j][k];

                    }

                }

                p[i].n = n / ;

                p[i].m = m;

            }

            gao();

        }

        if (m %  == ) {

            for (int i = ; i < ; ++i) {

                for (int j = ; j < n; ++j) {

                    for (int k = i * (m / ); k < (i + ) * m / ; ++k) {

                        p[i].a[j][k % (m / )] = a[j][k];

                    }

                }

                p[i].n = n;

                p[i].m = m / ;

            }

            gao();

        }

        if (n %  ==  && m %  == ) {

            for (int i = ; i < ; ++i) {

                for (int j = (i / ) * n / ; j < (i /  + ) * n / ; ++j) {

                    for (int k = (i % ) * m / ; k < (i %  + ) * m / ;

                            ++k) {

                        p[i].a[j % (n / )][k % (m / )] = a[j][k];

                    }

                }

                p[i].n = n / ;

                p[i].m = m / ;

            }

            gao();

        }

        s.n = n;

        s.m = m;

        for (int i = ; i < n; ++i)

            for (int j = ; j < m; ++j)

                s.a[i][j] = a[i][j];

        if (n < m) {

            s.rota();

            swap(n, m);

        }

        if ( * s.n ==  * s.m && s.m %  ==  && s.n %  == ) {

            for (int i = ; i < ; ++i) {

                for (int j = ; j < m; ++j) {

                    for (int k = i * m / ; k < (i + ) * m / ; ++k) {

                        p[i].a[j][k % (m / )] = s.a[j][k];

                    }

                }

                p[i].n = m;

                p[i].m = m / ;

            }

            for (int i = m; i < n; ++i)

                for (int j = ; j < m; ++j)

                    p[].a[i - m][j] = s.a[i][j];

            p[].n = n - m;

            p[].m = m;

            gao();

            for (int i = ; i < ; ++i) {

                for (int j = n - m; j < n; ++j) {

                    for (int k = i * m / ; k < (i + ) * m / ; ++k) {

                        p[i].a[j - (n - m)][k % (m / )] = s.a[j][k];

                    }

                }

                p[i].n = m;

                p[i].m = m / ;

            }

            for (int i = ; i < n - m; ++i)

                for (int j = ; j < m; ++j)

                    p[].a[i][j] = s.a[i][j];

            p[].n = n - m;

            p[].m = m;

            gao();

        }

        if (s.n ==  * s.m && s.m %  == ) {

            for (int i = ; i < n / ; ++i)

                for (int j = ; j < m / ; ++j)

                    p[].a[i][j] = s.a[i][j];

            p[].n = s.n / ;

            p[].m = s.m / ;

            for (int i = ; i < n / ; ++i)

                for (int j = m / ; j < m; ++j)

                    p[].a[i][j - m / ] = s.a[i][j];

            p[].n = s.n / ;

            p[].m = s.m / ;

            for (int i = n / ; i < n /  * ; ++i)

                for (int j = ; j < m; ++j)

                    p[].a[i - n / ][j] = s.a[i][j];

            p[].n = s.n / ;

            p[].m = s.m;

            for (int i = n /  * ; i < n; ++i)

                for (int j = ; j < m; ++j)

                    p[].a[i - n /  * ][j] = s.a[i][j];

            p[].n = n / ;

            p[].m = m;

            gao();

            for (int i = n / ; i < n /  * ; ++i)

                for (int j = ; j < m / ; ++j)

                    p[].a[i - n / ][j] = s.a[i][j];

            p[].n = s.n / ;

            p[].m = s.m / ;

            for (int i = n / ; i < n /  * ; ++i)

                for (int j = m / ; j < m; ++j)

                    p[].a[i - n / ][j - m / ] = s.a[i][j];

            p[].n = s.n / ;

            p[].m = s.m / ;

            for (int i = ; i < n / ; ++i)

                for (int j = ; j < m; ++j)

                    p[].a[i][j] = s.a[i][j];

            p[].n = s.n / ;

            p[].m = s.m;

            for (int i = n /  * ; i < n; ++i)

                for (int j = ; j < m; ++j)

                    p[].a[i - n /  * ][j] = s.a[i][j];

            p[].n = n / ;

            p[].m = m;

            gao();

            for (int i = n / ; i < n; ++i)

                for (int j = ; j < m / ; ++j)

                    p[].a[i - n / ][j] = s.a[i][j];

            p[].n = s.n / ;

            p[].m = s.m / ;

            for (int i = n / ; i < n; ++i)

                for (int j = m / ; j < m; ++j)

                    p[].a[i - n / ][j - m / ] = s.a[i][j];

            p[].n = s.n / ;

            p[].m = s.m / ;

            for (int i = ; i < n / ; ++i)

                for (int j = ; j < m; ++j)

                    p[].a[i][j] = s.a[i][j];

            p[].n = s.n / ;

            p[].m = s.m;

            for (int i = n / ; i < n / ; ++i)

                for (int j = ; j < m; ++j)

                    p[].a[i - n / ][j] = s.a[i][j];

            p[].n = n / ;

            p[].m = m;

            gao();

        }

        printf("%d\n", ans);

    }

    return ;

}

最新文章

  1. Android开发工具全面转向Android Studio(1)——准备开发环境
  2. hibernate学习（设计多对多 关系 映射）
  3. Inno Setup 卸载前关闭进程或服务 x86 x64
  4. springMVC源码分析之拦截器
  5. 教你写一个Android可快速复用的小键盘输入控件
  6. mina
  7. acdream Divide Sum
  8. iOS 的 Safari 文件上传功能详解
  9. JAVA算术运算符、关系运算符和位运算符
  10. Linux突然断电后文件丢失的问题
  11. Android 原生 Intent 分享支持的那些事
  12. Mysql Innodb 锁机制
  13. .NET Framework和 .Net Core实现不一致的API之 `EmailAddressAttribute`
  14. CenOS_命令帮助
  15. mac下启动mysql
  16. Spring事务mysql不回滚：mysql引擎修改
  17. Thread（26）
  18. Dubbo原理实现之与spring融合
  19. 树莓派安装.net core 2.1
  20. Ubuntu 16.04实现SSH无密码登录/免密登录/自动登录（ssh-keygen/ssh-copy-id）

热门文章

  1. java里有没有专门判断List里有重复的数据
  2. 树状数组求逆序对：POJ 2299、3067
  3. 设置TextView下划线并响应点击事件(SpannableString)
  4. C#_DataTable导出Execl为自定义标题
  5. form表单生成的简单理解
  6. Office 多版本共存
  7. 在IIS7.5打开网页的时候，提示： HTTP 错误 500.0 - Internal Server Error 调用 LoadLibraryEx 失败，在 ISAPI 筛选器 &quot;C:\Windows\Microsoft.NET\Framework\v4.0.30319\\aspnet_filter.dll&quot; 上。解决方法
  8. 使用TCP/IP的套接字（Socket）进行通信
  9. Apache Commons fileUpload实现文件上传之一
  10. 解决requestAnimationFrame的兼容问题