`
kmplayer
  • 浏览: 508745 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

输入是一个n*m的矩阵,要求找到其中最大的全0字矩阵

阅读更多
1,分析:
这个题其实就是最大子矩阵,只不过把0的权设为1,其他的权设为负无穷,这样求出来的肯定是最大的全是0的矩阵,仔细看一下我得做法,用的是动态规划。

2,实例代码:
#include <cstdio>

const int Max_Int = 0xfffffff;
int map[301][301],opt[301];
int n, m, maxn;

void init( )
{
    int i, j, t;
    scanf("%d%d", &n, &m);
    for ( i = 0; i < n; i++ )
        for ( j = 0; j < m; j++ )
        {
            scanf("%d", &t);
            if ( t == 0 )
                map[i][j] = 1;
            else
                map[i][j] = -Max_Int;
        }
    maxn = 0;
}

void work( )
{
    int i, j, k, t;
    for (i = 0; i < n; i++)
    {
        for (j = i; j < n; j++)
        {
            t = 0;
            for ( k = 0; k < m; k++ )
            {
                if (j == i)
                    opt[k] = map[i][k];
                else
                    opt[k] += map[j][k];
                t += opt[k];
                if (t < 0)
                    t = 0;
                if (maxn < t)
                    maxn = t;
            }
        }
    }
}

void print( )
{
    printf("%d", maxn);
}

int main( )
{
    init( );
    work( );
    print( );
    return 0;
}
分享到:
评论

相关推荐

    从键盘输入一个3*3的矩阵,要求:输出此矩阵对应的转置矩阵(所谓转置,指的是对任意元素Pi,j和对应的Pj,i交换)。

    从键盘输入一个3*3的矩阵,要求:输出此矩阵对应的转置矩阵(所谓转置,指的是对任意元素Pi,j和对应的Pj,i交换)。

    n*n矩阵行列转换

    输入任意行列数的矩阵,通过遍历半上三角形循环 来转换矩阵 运行界面很直观看出结果 原矩阵和转换之后的矩阵

    .Key_MxN ARM uC/OS-II下的M*N矩阵键盘模块Proteus仿真

    本文将详细介绍如何在ARM微处理器上,利用uC/OS-II实时操作系统实现一个M*N矩阵键盘模块,并进行Proteus仿真实现。我们将探讨矩阵键盘的工作原理、uC/OS-II任务调度以及Proteus仿真工具的使用。 首先,矩阵键盘的...

    螺旋阵,请设计算法完成螺旋阵的输出,具有要求为:输入一个m行n列的矩阵,按顺时针螺旋顺序输出矩阵中的所有元素

    请设计算法完成螺旋阵的输出,具有要求为:输入一个m行n列的矩阵,按顺时针螺旋顺序输出矩阵中的所有元素。 【输入】 第1行输入两个正整数m和n,表示m行n列的矩阵; 从第2行开始按行输入该矩阵的所有元素。 【输出】...

    输出任意n*m阶的螺旋矩阵

    如输入n=3,m=4,则输出 1 2 3 4 10 11 12 5 9 8 7 6 输入n=4,m=5,则输出 1 2 3 4 5 14 15 16 17 6 13 20 19 18 7 12 11 10 9 8 输入n=4,m=4,则输出 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7

    字符串问题,M*N矩阵实现

    P省感染分布情况地图是一个N*M的矩形,地图上的每个点有三种状态未感染、被感染和被保护,分别用大写字母O,X,P表示,实现输入一个地图和经历的病毒周期数,推算出经历了这些病毒周期后的新地图

    juzhenxiangcheng.rar_M?n_nested arrays_矩阵嵌套

    矩阵相乘的算法比较简单,输入一个m*n矩阵和一个n*p矩阵,结果必然是m*p矩阵,有m*p个元素,每个元素都需要计算,可以使用m*p嵌套循环进行计算。 根据矩阵乘法公式: 可以用循环直接套用上面的公式计算每个元素。...

    矩阵乘法源代码及思路.txt

    矩阵相乘最重要的方法是一般矩阵乘积。...一个m×n的矩阵就是m×n个数排成m行n列的一个数阵。由于它把许多数据紧凑地集中到了一起,所以有时候可以简便地表示一些复杂的模型,如电力系统网络模型。 [2]

    C语言矩阵乘法A

    从文件arr.in中读入一个m行k列的整数矩阵a和一个k行n列的整数矩阵b(1 &lt; m, k, n ),在标准输出上输出这两个矩阵的乘积。 【输入形式】 输入文件arr.in中有m + k + 1行,前m行是矩阵a的元素aij,第m + 1行是空行...

    螺旋矩阵 (M*N) 由外向内输入 完整注释

    实现由外向内螺旋矩阵的操作 矩阵大小为M*N 实现方法为递归调用 有完整注释,看起来比较轻松

    矩阵加法1

    2. **初始化结果矩阵**:根据给定的N和M,创建一个新的N行M列的矩阵,用于存储两矩阵相加的结果。 3. **逐元素相加**:遍历两个输入矩阵的每个元素,对应位置的元素相加,然后将结果存入结果矩阵的相应位置。例如,...

    元素放置(指针)XDOJ.cpp

    定义一个一维整形数组num[50],输入正整数m、n(2≤m≤n≤7),输入一个m*n整形矩阵(值小于100),编写函数place()完成矩阵元素S型放置,从小到大排列,使用指针完成地址传递,主函数完成数组输入和输出。...

    矩阵运算_C++_K._矩阵_

    D=A×B=(dij)m×q,其中dij=∑aik×bkj,k=12……n⑺ 设计一个菜单,具有求矩阵的转置、求矩阵的和、求矩阵的积、退出等基本的功能。在求矩阵的和或求矩阵的积时要求能够先提示输入两个矩阵的,然后再进行相应的操作...

    螺旋矩阵(C语言版)

    螺旋矩阵是指一个n×n的矩阵,其中的数字按照从外向内、顺时针方向螺旋填充。例如,一个3×3的螺旋矩阵可能如下所示: ``` 1 2 3 8 9 4 7 6 5 ``` ### 算法实现逻辑 生成螺旋矩阵的关键在于确定填充元素的顺序。...

    矩阵连乘问题 给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。

    例如,对于三个矩阵A、B、C,如果A是一个10×100的矩阵,B是一个100×5的矩阵,C是一个5×50的矩阵,则(A×B)×C需要的乘法次数为10×100×5 + 10×5×50 = 7500,而A×(B×C)需要的乘法次数为100×5×50 + 10×100...

    python矩阵连乘(动态规划)

    【输入形式】在屏幕上输入第1个矩阵的行数和第1个矩阵到第n个矩阵的列数,各数间都以一个空格分隔。 【输出形式】矩阵m,其中m(i,j)中存放的是:计算A[i:j](其中1&lt;=i&lt;=j&lt;=n)所需的最少数乘次数。 矩阵s,其中s[i]...

    螺旋矩阵的实现

    本例中,我们首先定义了一个固定大小的矩阵(这里设为10x10),然后根据用户输入的行数m和列数n来生成螺旋矩阵。接下来,我们将逐步解析代码中的关键部分,并解释其实现逻辑。 #### C语言螺旋矩阵实现详解 1. **...

    输入两个正整数m和n求其最大公约数和最小公倍数 (2).pdf

    这些题目涵盖了计算机科学基础的多个领域,包括算法设计、数据结构、输入输出处理、字符串操作、数学计算以及简单的逻辑判断。下面将逐一解析这些知识点: 1. **最大公约数(GCD)和最小公倍数(LCM)**:这是基本...

    求n阶矩阵逆矩阵

    矩阵逆矩阵是线性代数中一个非常重要的概念,它是矩阵乘法的逆操作,即矩阵A的逆矩阵B满足AB=BA=E,其中E是单位矩阵。矩阵逆矩阵的求解是线性代数中一个基本问题,它有很多实际应用,如线性方程组的解、矩阵分解、...

    C语言编写矩阵函数包(矩阵的加,减,乘,转置矩阵,逆矩阵)

    对于一个m×n矩阵A,其转置矩阵\( A^T \)的维度为n×m,计算规则为: \[ (A^T)_{ij} = A_{ji} \] 在提供的代码片段中,虽然没有直接给出转置函数的实现,但根据描述可知,可以通过类似的方法实现矩阵转置。即读取...

Global site tag (gtag.js) - Google Analytics