上海外贸网站制作公司南宁seo服务优化

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1081

题意：

给出N*N个数字构成的一个矩阵，每个数字的大小在[-127,127]之间，求出这个矩阵的和最大的子矩阵，输出最大和即可。

思路：

将n*n的矩阵转化为一维动态规划，需要将每一行的数据看做一个整体，然后再对row1,row2,...,rown做动态规划dp[n]=(dp[n-1]>0?dp[n-1]:0)+rown;子矩阵是由连续的行和连续的列组成，先枚举连续的列for(col_start=1;col_start<=n;col_start++){ for(col_end=col_start;col_end<=n;col_end++)}，rectangle[i][j]存的是第i行的前j项和，每行的连续列的求和式为rectangle[row][col_end]-rectangle[row][col_start-1]，每一行的和值即为构造的一维动态规划的序列元素，最后做一维动态规划即可。

#include <stdio.h>
int main()
{int n,row,col,col_start,col_end;int dp_before,dp_after,ans_max;int rectangle[105][105]={0};while(scanf("%d",&n)!=EOF){for(row=1;row<=n;row++){for(col=1;col<=n;col++){scanf("%d",&rectangle[row][col]);rectangle[row][col]=rectangle[row][col]+rectangle[row][col-1];}}ans_max=-1000000000;for(col_start=1;col_start<=n;col_start++){for(col_end=col_start;col_end<=n;col_end++){ dp_before=0;for(row=1;row<=n;row++){dp_after=(dp_before>0?dp_before:0)+(rectangle[row][col_end]-rectangle[row][col_start-1]);if(dp_after>ans_max)ans_max=dp_after;dp_before=dp_after;}}}printf("%d\n",ans_max);}return 0;
}