Gym - 101972G - Minimax（DP）

56 阅读 0 评论 37 点赞

我是靠谱客的博主粗暴羊，最近开发中收集的这篇文章主要介绍Gym - 101972G - Minimax（DP），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：戳一戳

题意：一个n*m的矩阵，用一行一列把矩阵分成4个部分，在这四个子矩阵中每个都有最大值，求这个四个最大值中的最大值减去最小值尽可能小，求最小的

题解：从四个角开始DP，a1[i][j] 表示从第 i 行到第 1 行，从第 j 列到第 1 列的子矩阵中的最大值，以此类推，然后枚举第i行第j列进行删除，查询四个角的最大值，求出最大的与最小的，然后选择（最大-最小）的值最小的，代码写的很详细了。。。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int a1[505][505] = {0};
int a2[505][505] = {0};
int a3[505][505] = {0};
int a4[505][505] = {0};
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, m;
        memset(a1,0,sizeof(a1));
        memset(a2,0,sizeof(a2));
        memset(a3,0,sizeof(a3));
        memset(a4,0,sizeof(a4));
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                int x;
                scanf("%d", &x);
                a1[i][j] = a2[i][j] = a3[i][j] = a4[i][j] = x;
            }
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                a1[i][j] = max(max(a1[i][j], a1[i - 1][j]), a1[i][j - 1]);
        for (int i = 1; i <= n; i++)
            for (int j = m; j > 0; j--)
                a2[i][j] = max(max(a2[i][j], a2[i - 1][j]), a2[i][j + 1]);
        for (int i = n; i > 0; i--)
            for (int j = 1; j <= m; j++)
                a3[i][j] = max(max(a3[i][j], a3[i + 1][j]), a3[i][j - 1]);
        for (int i = n; i > 0; i--)
            for (int j = m; j > 0; j--)
                a4[i][j] = max(max(a4[i][j], a4[i + 1][j]), a4[i][j + 1]);
        int ans = 0x3f3f3f3f;
        for (int i = 2; i < n; i++)
        {
            for (int j = 2; j < m; j++)
            {
                int ma = 0, mi = 0x3f3f3f3f;
                ma = max(ma, a1[i - 1][j - 1]);
                ma = max(ma, a2[i - 1][j + 1]);
                ma = max(ma, a3[i + 1][j - 1]);
                ma = max(ma, a4[i + 1][j + 1]);
                mi = min(mi, a1[i - 1][j - 1]);
                mi = min(mi, a2[i - 1][j + 1]);
                mi = min(mi, a3[i + 1][j - 1]);
                mi = min(mi, a4[i + 1][j + 1]);
                ans = min(ma - mi, ans);
            }
        }
        printf("%dn", ans);
    }
    return 0;
}