poj 1050 求和问题
题意：给定一个n*n的矩阵，求一个子矩阵，使得该矩阵的元素之和最大。
思路：经典的DP。由一维到二维。
??????1.必须先了解一维的情况，对于一维的数组而言，则转化为用DP求最大连续子序列，DP的状态方程为：sum[i] = max（sum[i-1] + num[i], 0)。
?????#include<iostream>using namespace std;const int Max = 105;int max(int a, int b){ return a > b ? a : b;}int main(){ int n, i, j, k, row, col, sum, ans; int num[Max][Max], now[Max]; cin >> n; row = col = n; for(i = 0; i < row; i ++) for(j = 0; j < col; j ++) cin >> num[i][j];ans = sum = 0;for(i = 0; i < row; i ++){memset(now, 0, sizeof(now));for(j = i; j < row; j ++) // 求第i行到第j行的子矩阵。for(k = 0, sum = 0; k < col; k ++){ now[k] += num[j][k];sum = max(sum + now[k], 0);if(sum > ans) ans = sum;}}cout << ans << endl;return 0;}
?
?
?
