本文主要是介绍Hdu 1081 To The Max -- DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*
题意：给你一个n*n的矩阵，充满数字。让你找到一个矩形区域，使得区域内数字和最大。
分析：将矩阵看做一列数字去求，求这一列数字中最大的片段和。但是怎么把矩阵压缩成一列呢？而且要保证其正确性？
从1-n行，每次从第i行往下加，得到n-i+1种情况。一共n*(n-1)/2种情况。完备和准确性都满足。
*/
#include<stdio.h>
#include<string.h>
int a[105][105];
int b[105];
#define Min -99999999
int main()
{
int n,ans;
while(~scanf("%d",&n))
{
ans = Min;
memset(a,0,sizeof(a));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d",&a[i][j]);
for (int i = 1; i <= n; i++)//以第i行为第一行开始往下加，每回得到n-i+1列数字。总共需要求n*(n-1)/2次。
{
memset(b,0,sizeof(b));
for (int j = i; j <= n; j++)
{
for (int k = 1; k <= n; k++)
{
b[k] += a[j][k];
}
//O(n)的方法求最大片段和。
int tem1 = b[1];
int tem2 = tem1;
for (int i = 2; i <= n; i++)
{
if(tem1>0)tem1 += b[i];
else tem1 = b[i];
if(tem2 < tem1) tem2 = tem1;
}
if(tem2 > ans)
ans = tem2;
}
}
printf("%d\n",ans);
}
return 0;
}这篇关于Hdu 1081 To The Max -- DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
