OpenJudge 2766 最大子矩阵
2024-10-18 19:28:16
1.链接:
http://bailian.openjudge.cn/practice/2766
2.题目:
- 总Time Limit:
- 1000ms
- Memory Limit:
- 65536kB
- Description
- 已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。
比如,如下4 * 4的矩阵
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2的最大子矩阵是
9 2
-4 1
-1 8这个子矩阵的大小是15。
- Input
- 输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。再后面的若干行中,依次(首先从左到右给出第一行的N个整数,再从左到右给出第二行的N个整数……)给出矩阵中的N2个整数,整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[-127, 127]。
- Output
- 输出最大子矩阵的大小。
- Sample Input
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1 8 0 -2- Sample Output
15- Source
- 翻译自 Greater New York 2001 的试题
3.思路:
拓展的最大字段和。先遍历行的所有可能情况k=1-n。然后计算k行的矩阵每列的和,转为一维,在用最大字段和的方法求最大。
4.代码:
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std; int main()
{
//freopen("C://input.txt","r",stdin); int i,j,k; int n;
cin >> n; int **arr_matrix = new int*[n];
for(i = ; i < n; ++i) arr_matrix[i] = new int[n]; for(i = ;i < n; ++i)
{
for(j = ;j < n; ++j)
{
cin >> arr_matrix[i][j];
}
} int *arr_temp = new int[n]; int *dp = new int[n]; int max_sum = arr_matrix[][];
for(k = ; k < n; ++k)
{
memset(arr_temp,,sizeof(int) * n);
for(j = ; j < n; ++j)
{
for(i = ; i < k; ++i) arr_temp[j] += arr_matrix[i][j];
} for(i = k; i < n; ++i)
{
for(j = ; j < n; ++j) arr_temp[j] += arr_matrix[i][j]; memset(dp,,sizeof(int) * n);
dp[] = arr_temp[];
for(j = ; j < n; ++j)
{
dp[j] = ((dp[j - ] + arr_temp[j]) > arr_temp[j]) ? (dp[j - ] + arr_temp[j]) : arr_temp[j];
if(max_sum < dp[j]) max_sum = dp[j];
} for(j = ; j < n; ++j) arr_temp[j] -= arr_matrix[i - k][j];
}
} cout << max_sum << endl; delete [] dp; delete [] arr_temp; for(i = ; i < n; ++i) delete [] arr_matrix[i];
delete [] arr_matrix; return ;
}
最新文章
- linux查看端口占用情况
- Mongodb 的基本使用
- Android 如何在Eclipse中查看Android API源码 及 support包源码
- seajs中spm压缩工具使用
- yii2.0 控制器加载不同的user组件
- 一起刷LeetCode1-Two Sum
- hdu1863 畅通工程(最小生成树之prim)
- 学习Swift -- 数组(Array) - 持续更新
- 直接拿来用的15个jQuery代码片段
- Tomcat7 + JRebel6.3.0 + IntelliJ idea 热部署配置过程+错误分析
- 它们的定义dialog
- JSTL c标签,fn标签,fmt标签 - 生活在爪洼岛上 - ITeye技术网站
- Eight hdu 1043 八数码问题 双搜
- UVA - 247 Calling Circles Floyd判圈
- 单周期CPU设计的理论基础
- C++11 自动推导auto
- JDBC排序数据实例
- C#数据库连接方法
- CSS(一)sytle
- P1346 电车