poj 1050 To the Max(最大子矩阵之和)
poj 1050 To the Max(最大子矩阵之和)
xindoo
发布于 2021-01-22 12:56:11
发布于 2021-01-22 12:56:11
http://poj.org/problem?id=1050
我们已经知道求最大子段和的dp算法 参考 here 也可参考编程之美有关最大子矩阵和部分。
然后将这个扩大到二维就是这道题。顺便说一下，有时候不要把问题想复杂了，有些问题只能靠暴力求解，而这道题是暴力加算法。
在这个题中，我们可以把二维压缩到一维然后求解最大子段。我们先枚举所求矩阵的起点行和结束行，然后把每一列的数据之和求出，用这些数据和就构造出一个一维的数组（代码中我没有明确表示出这个数组），然后用最大子段和的dp算法求解。
关于二维压缩到一维的过程，适当处理可以大大减小时间复杂度。
最终时间复杂度是O(n^3)；
我的代码，思路是正确的，但是提交上去之后wa了，求大神赐教。
//2013-06-26-08.45
//poj 1050
#include <iostream>
#include <string.h>
#include <algorithm>
int map[103][103];
int sum[103][103];
using namespace std;
int main()
{
int n;
while (cin >> n)
{
memset(sum, 0, sizeof(sum));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> map[i][j];
sum[i][j] = map[i][j] + sum[i-1][j];
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < i; j++)
{
int tol = 0;
for (int k = 1; k <= n; k++)
{
if (sum[i][k]-sum[j][k] < 0) //这个地方就是压缩后的数组
tol = 0;
else
tol += (sum[i][k]-sum[j][k]);
if (tol > ans)
ans = tol;
}
}
}
cout << ans << endl;
}
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2013-06-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
相关产品与服务
文件存储
文件存储（Cloud File Storage，CFS）为您提供安全可靠、可扩展的共享文件存储服务。文件存储可与腾讯云服务器、容器服务、批量计算等服务搭配使用，为多个计算节点提供容量和性能可弹性扩展的高性能共享存储。腾讯云文件存储的管理界面简单、易使用，可实现对现有应用的无缝集成；按实际用量付费，为您节约成本，简化 IT 运维工作。