HDU 2830(动态规划)

╰+攻爆jí腚メ 2022-06-05 03:22 161阅读 0赞

问题描述:

Given an N \* M matrix with each entry equal to 0 or 1. We can find some rectangles in the matrix whose entries are all 1, and we define the maximum area of such rectangle as this matrix’s goodness.   
  
We can swap any two columns any times, and we are to make the goodness of the matrix as large as possible.

Input

There are several test cases in the input. The first line of each test case contains two integers N and M (1 ≤ N,M ≤ 1000). Then N lines follow, each contains M numbers (0 or 1), indicating the N \* M matrix

Output

Output one line for each test case, indicating the maximum possible goodness

Sample Input

3 4
    1011
    1001
    0001
    3 4
    1010
    1001
    0001

Sample Output

4
    2

题目分析:给我们一个矩阵，问我们最大全1矩阵的面积。注意矩阵的每一列都可以交换。

题目题意:预处理一下就好了，其实都不算dp的

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    
    const int maxn=1e3+100;
    char arr[maxn][maxn];
    int dp[maxn][maxn];
    bool cmp(int a,int b)
    {
        return a>b;
    }
    int main()
    {
        int n,m;
        while (scanf("%d%d",&n,&m)!=EOF) {
            for (int i=1;i<=n;i++) {
                scanf("%s",arr[i]+1);
            }
            memset (dp,0,sizeof (dp));
            for (int j=1;j<=m;j++) {
                for (int i=n;i>=1;i--) {
                    if (arr[i][j]=='1') dp[i][j]=dp[i+1][j]+1;
                    else dp[i][j]=0;
                }
            }
            int ans=0;
            for (int i=1;i<=n;i++) {
                sort(dp[i]+1,dp[i]+1+m,cmp);
                int res=0;
                for (int j=1;j<=m;j++)
                    res=max(res,dp[i][j]*j);
                ans=max(ans,res);
            }
            printf("%d\n",ans);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，161人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu1087 动态规划

Super Jumping! Jumping! Jumping! Time Limit: 2000/1000 MS (Java/Others) Memory Lim

淡淡的烟草味﹌/ 2022年08月03日 05:14/ 0 赞/ 165 阅读

相关 HDU 1421(动态规划)

问题描述: 搬寝室是很累的,xhd深有体会.时间追述2006年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因

素颜马尾好姑娘i/ 2022年06月06日 14:38/ 0 赞/ 167 阅读

相关 HDU 1176(动态规划)

问题描述: 都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的

刺骨的言语ヽ痛彻心扉/ 2022年06月06日 03:28/ 0 赞/ 193 阅读

相关 HDU 1231(动态规划)

问题描述: 给定K个整数的序列\{ N1, N2, ..., NK \}，其任意连续子序列可表示为\{ Ni, Ni+1, ..., Nj \}，其中 1 <= i <

绝地灬酷狼/ 2022年06月06日 00:57/ 0 赞/ 186 阅读

相关 HDU 2830(动态规划)

问题描述: Given an N \ M matrix with each entry equal to 0 or 1. We can find some rectangle

╰+攻爆jí腚メ/ 2022年06月05日 03:22/ 0 赞/ 162 阅读

相关 HDU 1978(动态规划)

问题描述这是一个简单的生存游戏，你控制一个机器人从一个棋盘的起始点(1,1)走到棋盘的终点(n,m)。游戏的规则描述如下： 1.机器人一开始在棋盘的起始点并有起始点所

怼烎@/ 2022年06月03日 03:25/ 0 赞/ 160 阅读

相关动态规划hdu2501

本文依旧是动态规划的题，杭电的2501题。有一个大小是 2 x n 的网格，现在需要用2种规格的骨牌铺满，骨牌规格分别是 2 x 1 和 2 x 2，请计算一共有多少种铺设

绝地灬酷狼/ 2022年06月01日 13:36/ 0 赞/ 173 阅读

相关动态规划HDU—1176

免费馅饼 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Othe

柔情只为你懂/ 2022年06月01日 13:22/ 0 赞/ 185 阅读

相关 HDU 2830 Matrix Swapping II

原题目链接：[HDU2845][] -------------------- 分类 HDU 动态规划贪心 -------------------- 题意

悠悠/ 2022年04月16日 06:25/ 0 赞/ 114 阅读

相关 HDU 2830 Matrix Swapping II

Matrix Swapping II Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/3276

谁借莪１个温暖的怀抱￠/ 2022年03月29日 05:48/ 0 赞/ 106 阅读