小美的平衡矩阵_dp思路

这篇具有很好参考价值的文章主要介绍了小美的平衡矩阵_dp思路。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

小美的平衡矩阵


写在前面:
本博客只是一种解题思路的提供。

小美的平衡矩阵

题目描述:

小美拿到了一个n*n 的矩阵,其中每个元素是 0 或者 1。
小美认为一个矩形区域是完美的,当且仅当该区域内 0 的数量恰好等于 1 的数量。
现在,小美希望你回答有多少个i*i的完美矩形区域。你需要回答1<=i<=n的所有答案。

输入描述

第一行输入一个正整数n,代表矩阵大小。
接下来的n行,每行输入一个长度为n的01 串,用来表示矩阵。

输出描述

输出n行,第i行输出的I*I 完美矩形区域的数量。

示例 1
输入
4
1010
0101
1100
0011
输出
0
7
0
1

思路:

  • 符合条件的矩阵的边一定是偶数,只有偶数才能保证 0和1的数量相等

  • 确定一个矩阵只需要确定这个矩阵的四个顶点中的一个和边长m,这里选择右下角的顶点

  • a r r [ i ] [ k ] arr[i][k] arr[i][k] 记录了原始输入的 n ∗ n n*n nn的矩阵

  • d p [ m ] [ i ] [ k ] dp[m][i][k] dp[m][i][k] 的含义是 当边长为 m 时 , 右下角为 a r r [ i ] [ k ] 时的矩阵内数字和 当边长为m时,右下角为arr[i][k]时的矩阵内数字和 当边长为m,右下角为arr[i][k]时的矩阵内数字和

  • 当矩阵内和为矩阵元素个数一半时,他是平衡矩阵。也就是说 当 m 2 2 = = d p [ m ] [ i ] [ k ] 时 \frac{m^2}{2} == dp[m][i][k]时 2m2==dp[m][i][k] ,这个矩阵是平衡矩阵

这里放一个 d p [ i ] [ k ] dp[i][k] dp[i][k]的版本,此时 d p [ i ] [ k ] dp[i][k] dp[i][k]的含义为:以 a r r [ 1 ] [ 1 ] arr[1][1] arr[1][1]为左上元素, a r r [ i ] [ k ] arr[i][k] arr[i][k]为右下角元素的这个框内的所有元素和,此时的平衡矩阵的个数并不在dp中保存,而是作为一个临时变量存储(这一点切记)。

#include<iostream>
#include<vector>
#include<string>
using namespace std;

int main(){

    int N,n,i=1,k;// N用于控制输入,n用于控制输出,i和k用于访问数组的元素
    cin>>N;
    string s;// 用于记录输入的01串
    n = N;
    vector<vector<int>> arr(N+1,vector<int>(N+1));
    vector<vector<int>> dp(N+1,vector<int>(N+1));
    
    while(N--){
        k = 1;
        while(k<=n){
            cin>>s;
            for(char ch:s){// 遍历01串中的每个字符,将其数字放入arr中
                arr[i][k++] = ch-'0';
            }
            ++i;
        }
    }
    // 计算dp数组
    for(i = 1;i<=n;++i){
        for(k = 1;k<=n;++k){
            dp[i][k] = dp[i-1][k]+dp[i][k-1]-dp[i-1][k-1]+arr[i][k];            
        }
    }

    for(int m = 1;m<=n;++m){// 矩阵边长为1开始遍历,直到边长为n
        int ans = 0;
        if(m%2==0){// 只有边长为偶数的矩阵内才有可能使得 0和1的数目相等,保证可能存在平衡矩阵
            for(i = 1;i<=n;++i){
                for(k = 1;k<=n;++k){
                    if(i>=m&&k>=m){
                        unsigned long long num = dp[i][k]-dp[i-m][k]-dp[i][k-m]+dp[i-m][k-m];
                        if(num==m*m/2)
                            ans++;
                    }
                }
            }
        }
        cout<<ans<<endl;
    }

    return 0;
}

有什么问题欢迎来讨论。


最开始思路:

d p [ r ] [ q ] [ i ] [ k ] dp[r][q][i][k] dp[r][q][i][k] 保存 以 a r r [ r ] [ q ] arr[r][q] arr[r][q]为左上角 a r r [ i ] [ k ] arr[i][k] arr[i][k] 为右下角的框内的元素和,发现dp的初始化和计算都比较麻烦,而且也计算了很多不符合条件的框(非正方形框)

稍微改进

d p [ m ] [ i ] [ k ] dp[m][i][k] dp[m][i][k] 保存 边长为 m m m时,框的右下角为元素 a r r [ i ] [ k ] arr[i][k] arr[i][k]时的这个框内的所有元素和,刨除了非正方形的框,

最后:

d p [ i ] [ k ] dp[i][k] dp[i][k] ,也就是代码版本文章来源地址https://www.toymoban.com/news/detail-842564.html

注意:本程序仅由简单测试,主要是提供思路。

到了这里,关于小美的平衡矩阵_dp思路的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • CCF-CSP真题《202305-2 矩阵运算》思路+python,c++满分题解

    想查看其他题的真题及题解的同学可以前往查看:CCF-CSP真题附题解大全 试题编号: 202305-2 试题名称: 矩阵运算 时间限制: 5.0s 内存限制: 512.0MB 问题描述: Softmax(Q×KTd)×V 是 Transformer 中注意力模块的核心算式,其中 Q、K 和 V 均是 n 行 d 列的矩阵,KT 表示矩阵 K 的

    2024年02月16日
    浏览(46)
  • 动态规划算法学习一:DP的重要知识点、矩阵连乘算法

    三部曲如下三步: 基本原则:“空间换时间” 存储重复子问题的解,减少运算时间 底层运算:“表格操作” 用表格存储子问题的解 实现路线:“子问题划分、自底向上求解” 利用表格中存储的子问题的解,求上一层子问题的解。 矩阵连乘计算次序 可以用 加括号的方式

    2024年02月09日
    浏览(39)
  • 「算法小记」-2:矩阵链相乘的方案数【迭代/递归/动态规划/区域化DP/记忆化搜索】(C++ )

    😎 作者介绍:我是程序员洲洲,一个热爱写作的非著名程序员。CSDN全栈优质领域创作者、华为云博客社区云享专家、阿里云博客社区专家博主、前后端开发、人工智能研究生。公粽号:程序员洲洲。 🎈 本文专栏:本文收录于洲洲的《算法小记》系列专栏,该专栏记录了许

    2024年02月05日
    浏览(50)
  • 对动态 DP 和全局平衡二叉树的一点补充解释

    说明:最近在帮高中竞赛教练写讲义,这是本人对讲义中动态 DP 内容的补充解释(因为主要是对知识点的理解,不太容易用通用的语言表述,也不适合作为讲义内容供读者阅读,所以用的是补充注释的形式)。 写的比较抽象也比较初等,仅供意会 。 我们先从一般的角度,用

    2024年02月11日
    浏览(32)
  • 华为OD机试 -矩阵扩散(Java) | 机试题+算法思路+考点+代码解析 【2023】

    存在一个mn的二维数组,其成员取值范围为0或1。其中值为1的成员具备扩散性,每经过1S,将上下左右值为0的成员同化为1。二维数组的成员初始值都为0,将第[i,j]和[k,l]两个个位置上元素修改成1后,求矩阵的所有元素变为1需要多长时间。 输入描述: 输出数据中的前2个数字表

    2024年02月16日
    浏览(58)
  • 华为OD机试 -矩阵最大值(Java) | 机试题+算法思路+考点+代码解析 【2023】

    给定一个仅包含0和1的N*N二维矩阵,请计算二维矩阵的最大值,计算规则如下: 1、 每行元素按下标顺序组成一个二进制数(下标越大越排在低位),二进制数的值就是该行的值。矩阵各行值之和为矩阵的值。 2、允许通过向左或向右整体循环移动每行元素来改变各元素在行中

    2024年02月13日
    浏览(53)
  • 【华为OD机试真题 C++语言】68、矩阵扩散 | 机试题+算法思路+考点+代码解析

    🍂个人博客首页: KJ.JK   🍂专栏介绍: 华为OD机试真题汇总,定期更新华为OD各个时间阶段的机试真题,每日定时更新,本专栏将使用C++语言进行更新解答,包含真题,思路分析,代码参考,欢迎大家订阅学习 🎃题目描述 存在一个m*n的二维数组,其成员取值范围为0或1

    2024年02月16日
    浏览(58)
  • 【华为OD机试真题 Java语言】68、矩阵扩散 | 机试题+算法思路+考点+代码解析

    🍂个人博客首页: KJ.JK   🍂专栏介绍: 华为OD机试真题汇总,定期更新华为OD各个时间阶段的机试真题,每日定时更新,本专栏将使用Java语言进行更新解答,包含真题,思路分析,代码参考,欢迎大家订阅学习 🎃题目描述 存在一个m*n的二维数组,其成员取值范围为0或1  

    2024年02月14日
    浏览(50)
  • 【华为OD机试真题 Python语言】68、矩阵扩散 | 机试题+算法思路+考点+代码解析

    🍂个人博客首页: 鲨鱼狼臧   🍂专栏介绍: 2023华为OD机试真题,使用Python进行解答,专栏每篇文章都包括真题,思路参考,代码分析,订阅有问题后续可与博主解答问题 🎃题目描述 存在一个m*n的二维数组,其成员取值范围为0或1   其中值为1的成员具备扩散性,每经过

    2024年02月15日
    浏览(51)
  • Atcoder beginner contest 336 -- E -- Digit Sum Divisible --- 题解(数位dp)

    目录   E -- Digit Sum Divisibl 题目大意: 思路解析: 代码实现: 给你一个整数n,让你找出小于等于n的数中一共有多少个好整数,并输出好整数的个数。对好整数的个数定义为如果一个数能被他的数位之和整除,则称这个数为好整数。例如 12 能被 3 整除。 n=10^14。 看到数位之和

    2024年01月16日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包