POJ 1050 To the Max（动态规划、最大子矩阵和）

本文主要是介绍POJ 1050 To the Max（动态规划、最大子矩阵和），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击打开链接

题意：求最大子矩阵和。

将此问题转化为求多个最大子段和（行）的问题即可。

如：先求出第一行(a[0])的最大子字和，再将第二行a[1]的所有元素分别加到a[0]上去，再计算a[0]的最大子段和。

枚举所有起点行和终点行，得到的最大值即为答案。O（n^3），AC / 16MS。

//poj 1050 - dp
//2014-6-11
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX_N = 111;
int n;
int a[MAX_N][MAX_N];
//int d[MAX_N][MAX_N][MAX_N];int inline getMax ( int a, int b, int c )
{return max ( a, max ( b, c ) );
}int d[MAX_N][MAX_N];
void dp()
{memset ( d, 0, sizeof ( d ) );//answerint Max = -128;//calculate the max sum of sub-matrix(sub-segment) of line i to j//i-th linefor ( int i = 0; i < n; i++ ){//j-th linefor ( int j = i; j < n; j++ ){int b = 0;//k-th cowfor ( int k = 0; k < n; k++ ){//add the j-th line element to the i-th lineif ( j > i ){a[i][k] += a[j][k];}//calculate the max sum of sub-segment.if ( b > 0 ){b += a[i][k];}else{b = a[i][k];}Max = max ( Max, b );}}}printf ( "%d\n", Max );
}int main()
{freopen ( "in.txt", "r", stdin );scanf ( "%d", &n );for ( int i = 0; i < n; i++ ){for ( int j = 0; j < n; j++ ){scanf ( "%d", &a[i][j] );}}dp();return 0;
}

这篇关于POJ 1050 To the Max（动态规划、最大子矩阵和）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---