URAL 1146 Maximum Sum（最大子矩陣的和 DP）

Maximum Sum

大意：給你一個n*n的矩陣，求最大的子矩陣的和是多少。

思路：最開始我想的是預處理矩陣，遍歷子矩陣的端點，發現復雜度是O(n^4)。就不知道該怎么辦了。問了一下，是壓縮矩陣，轉換成最大字段和的問題。

壓縮行或者列都是能夠的。

int n, m, x, y, T, t;
int Map[1010][1010];int main()
{while(~scanf("%d", &n)){memset(Map, 0, sizeof(Map));for(int i = 1; i <= n; ++i){for(int j = 1; j <= n; ++j){scanf("%d", &t);Map[i][j] = Map[i-1][j]+t;}}int Max = -INF;for(int i = 1; i <= n; ++i){for(int j = i; j <= n; ++j){int sum = 0;for(int k = 1; k <= n; ++k){sum = sum<0?

0:sum; sum += Map[j][k]-Map[i-1][k]; Max = max(sum, Max); } } } printf("%d\n", Max); } return 0; }