poj - 1050 - To the Max（dp）

题意：一个N * N的矩阵，求子矩阵的最大和(N <= 100, -127 <= 矩阵元素 <= 127)。

题目链接：http://poj.org/problem?id=1050

——>>将二维压缩为一维，对一维进行dp求解。

将二维压缩成一维：

1、第1行

2、第2行加第1行

3、第3行加第2行加第1行

……

N、第N行加第N-1行加……加第1行

1、第2行

2、第3行加第2行

……

1、第N行

对于一维情况，设dp[i]表示以第i个元素结尾的最大连续和，则状态转移方程为：

dp[i] = max(nBuf[i], dp[i - 1] + nBuf[i]);

加上滚动数组思想优化空间。。

总时间复杂度：O(N ^ 3)

#include <cstdio>
#include <cstring>
#include <algorithm>using std::max;const int MAXN = 100 + 1;
const int INF = 0x3f3f3f3f;int N;
int nMatrix[MAXN][MAXN];void Read()
{for (int i = 1; i <= N; ++i){for (int j = 1; j <= N; ++j){scanf("%d", &nMatrix[i][j]);}}
}void Dp()
{int nRet = -INF;int nBuf[MAXN];for (int i = 1; i <= N; ++i){memset(nBuf, 0, sizeof(nBuf));for (int j = i; j <= N; ++j){for (int k = 1; k <= N; ++k){nBuf[k] += nMatrix[j][k];}int dp = 0;for (int k = 1; k <= N; ++k){dp = max(nBuf[k], dp + nBuf[k]);nRet = max(nRet, dp);}}}printf("%d\n", nRet);
}int main()
{while (scanf("%d", &N) == 1){Read();Dp();}return 0;
}