hdu2830 可交换行的最大子矩阵
最大 矩阵 交换
2023-09-11 14:14:00 时间
题意:
求最大子矩阵,但是相邻的列之间可以相互交换...
思路:
回想下固定的情况,记得那种情况是开俩个数组 L[i] ,R[i],记录小于等于i的最左边和最右边在哪个位置,对于这个题目,可以交换,也就是说顺序是可以自己随意更改的,那么我们直接sort一便,然后在找最大就行了,说下具体过程,便于理解
开始我们创建一个数组dp[i] ,记录第i列到当前j的位置的连续最大子序列,我们假设每一样都是矩形的下低,我们在开个数组tmp记录所有的dp,然后sort,之后可以开个数组L,R什么的,
但也可以不开,因为排序的原因,我们只要这样就行了
for(j = 1 ;j <= m ;j ++) ans = maxx(ans ,dp[j] * j);(这个是从大到小排序)
或者 for(j = m ;j >= 1 ;j --) ans = maxx(ans ,dp[j] * (m - j + 1));(从小到大)
求最大子矩阵,但是相邻的列之间可以相互交换...
思路:
回想下固定的情况,记得那种情况是开俩个数组 L[i] ,R[i],记录小于等于i的最左边和最右边在哪个位置,对于这个题目,可以交换,也就是说顺序是可以自己随意更改的,那么我们直接sort一便,然后在找最大就行了,说下具体过程,便于理解
开始我们创建一个数组dp[i] ,记录第i列到当前j的位置的连续最大子序列,我们假设每一样都是矩形的下低,我们在开个数组tmp记录所有的dp,然后sort,之后可以开个数组L,R什么的,
但也可以不开,因为排序的原因,我们只要这样就行了
for(j = 1 ;j <= m ;j ++) ans = maxx(ans ,dp[j] * j);(这个是从大到小排序)
或者 for(j = m ;j >= 1 ;j --) ans = maxx(ans ,dp[j] * (m - j + 1));(从小到大)
任选一个都行,无所谓..时间复杂度是O(n * m + lg(m));
#include<stdio.h> #include<string.h> #include<algorithm> #define N (1000 + 100) #define INF -1000000000 using namespace std; int dp[N]; int tmp[N]; char str[N]; int main () { int n ,m ,i ,j ,num ,ans; while(~scanf("%d %d" ,&n ,&m)) { ans = INF; memset(dp ,0 ,sizeof(dp)); for(i = 1 ;i <= n ;i ++) { scanf("%s" ,&str); for(j = 0 ;j < m ;j ++) { if(str[j] - '0') dp[j+1]++; else dp[j+1] = 0; tmp[j+1] = dp[j+1]; } sort(tmp + 1 ,tmp + m + 1); for(int ii = m ;ii >= 1 ;ii --) { if(!tmp[ii]) break; if(ans < tmp[ii] * (m - ii + 1)) ans = tmp[ii] * (m - ii + 1); } } printf("%d\n" ,ans); } return 0; }
相关文章
- nyoj 最大和 104 (二维子矩阵 DP) 好题
- 最大子数组 && 最大子矩阵
- Java实现最大连续子数组和
- Java实现 LeetCode 827 最大人工岛(DFS+暴力模拟)
- Java实现第十届蓝桥杯最大降雨量
- Java实现最大连续子数组和
- Java实现 蓝桥杯 乘积最大
- (算法)最大子数组和以及最大子矩阵和
- LeetCode-643. 子数组最大平均数 I
- 628. 三个数的最大乘积 ——【Leetcode每日一题】
- 86. 有没有设置能够限制 ABAP 数据库表能够存储的最大记录数?
- 华为OD机试 - 判断一组不等式是否满足约束并输出最大差(Java & JS & Python)
- 编程笔试(解析及代码实现):从矩阵中寻找和最大的子矩阵(首先需要将一个列表转为一个方矩阵)
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-939 区间最大和
- 力扣——1946. 子字符串突变后可能得到的最大整数(Java、python3实现)
- 1921. 消灭怪物的最大数量
- 习题 3.9 有3个整数a,b,c,由键盘输入,输出其中最大的数。
- Leetcode643. 子数组最大平均数 I(超时?)
- Leetcode 18. 最大单词长度乘积
- C/C++中各种类型int、long、double、char表示范围(最大最小值)
- BZOJ 3261 最大异或和 可持久化Trie树
- NYOJ 104 最大子矩阵(二维DP)
- 拉格朗日和kkt公式的应用示例 无论求解最大还是最小值,u都是>=0哈!最大是+ 最小是- 至少知道kkt是什么了 至于为什么可以转换再说吧
- 01二维矩阵中最大全为1的正方形maxSquare——经典DP问题(二维)
- 第十三届蓝桥杯JavaB组省赛F题——最大子矩阵 (AC)
- MySQL 查看当前最大连接数,并发数