学步园

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

解题思路：这道题是个DP问题，如果用穷举的方法的话，时间复杂度为O（N^4），会超时，所以我们就考虑用DP的方法。

#include <stdio.h><br /> #include <string.h></p> <p>int main()<br /> {<br /> const int size = 101;<br /> int Max,sum;<br /> int N,i,j,k,val,a[size][size];<br /> while (scanf("%d",&N)!=EOF)<br /> {<br /> memset(a,0,sizeof(a));<br /> Max = -128;<br /> for(i=1;i<=N;i++)<br /> for(j=1;j<=N;j++)<br /> {<br /> scanf("%d",&val);<br /> a[i][j]+=a[i][j-1]+val;//a[i][j]表示第i行前j个数之和<br /> }<br /> for(i=1;i<=N;i++)<br /> for (j=i;j<=N;j++)<br /> for(sum = 0,k=1;k<=N;k++)<br /> {<br /> //a[k][j]-a[k][i-1]表示第k行第j列与第i列之间的数<br /> sum=(sum>0?sum:0)+a[k][j]-a[k][i-1];<br /> if(sum>Max)<br /> Max = sum;<br /> }<br /> printf("%d/n",Max);<br /> }<br /> }