codeforces 1581 C - Portal（二维前缀和+二维前缀最小值）

本文主要是介绍codeforces 1581 C - Portal（二维前缀和+二维前缀最小值），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接
题意：
\(n×m\)的\(01\)矩阵，每次操作可反转任一格子内的值，求使得某一子矩阵内部全为\(0\)，边界全为\(1\)，四个角可为任意值得最少操作数。

思路：
二维前缀和处理，很明显枚举上下边界、左右边界可求最少操作数，复杂度为\(O(n^2m^2)\)。进行优化，先枚举上下边界，再枚举右边界，假设当前右边界为\(k(k>=4)\)，可构成矩阵\([1、2...、k-3，k]\)（上下边界已确定）。单独计算矩阵的一部分（列\(k-2，k-1，k\)，列\(k-2\)不是边界）需要的操作数\(ret\)，则当前答案最优值为\(min(ret+pre)\)=\(ret+min(pre)\)，\(pre\)为矩阵一部分（列\(k-3，k-4，...，i，\)\(1<=i<=k-3\)，列\(i\)是矩阵边界）需要的操作数，\(pre\)需遍历一遍不断更新。

code:

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#include <unordered_map>

#define fi first
#define se second
#define pb push_back
// #define endl "\n"
#define debug(x) cout << #x << ":" << x << endl;
#define bug cout << "********" << endl;
#define all(x) x.begin(), x.end()
#define lowbit(x) x & -x
#define fin(x) freopen(x, "r", stdin)
#define fout(x) freopen(x, "w", stdout)
#define ull unsigned long long
#define ll long long 

const double eps = 1e-15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1.0);
const int mod =  1e9 + 7;
const int maxn = 2e5 + 10;

using namespace std;

int s[410][410], sum[410][410], n, m;

int f(int lx, int ly, int rx, int ry){
    return sum[rx][ry] - sum[rx][ly - 1] - sum[lx - 1][ry] + sum[lx - 1][ly - 1];
}

void solve(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++)scanf("%1d", &s[i][j]);
    }
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + s[i][j];
        }
    }
    int ans = inf;
    for(int i = 1; i <= n; i ++){
        for(int j = i + 4; j <= n; j ++){
            int pre = inf;
            for(int k = 4; k <= m; k ++){
               int a1 = f(i + 1, k - 2, j - 1, k - 1);
               a1 += 2 - f(i, k - 2, i, k - 1) + 2 - f(j, k - 2, j, k - 1) + j - i - 1 - f(i + 1, k, j - 1, k);
               int ret1 = j - i - 1 - f(i + 1, k - 3, j - 1, k - 3);
               int ret2 = 2 - s[i][k - 3] - s[j][k - 3] + f(i + 1, k - 3, j - 1, k - 3);
               pre = min(pre + ret2, ret1);
               ans = min(ans, pre + a1);
            }
        }
    }
    printf("%d\n", ans);
}

int main(){
    int t;
    scanf("%d", &t);
    while(t --)solve();
    return 0;
}

这篇关于codeforces 1581 C - Portal（二维前缀和+二维前缀最小值）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！