#include<stdio.h>
#include<stdlib.h>
int sumofsubrect(int **s, int r1, int c1, int r2, int c2)
{
	int sum=0,i,j;
	for(i=r1;i<=r2;i++)
		for(j=c1;j<=c2;j++)
			sum=sum+s[i][j];
		return sum;
}
int main()
{
	int i,j,n,max,r,c,temp,**s;
	int **a;
	scanf("%d",&n);
	s=(int**)malloc(n*sizeof(int*));
	a=(int**)malloc(n*sizeof(int*));
	for(i=0;i<n;i++)
	{
		s[i]=(int*)malloc(n*sizeof(int));
		a[i]=(int*)malloc(n*sizeof(int));
	}
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			scanf("%d",&s[i][j]);
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			max=s[i][j];
			for(r=0;r<=i;r++)
				for(c=0;c<=j;c++)
				{
					temp=sumofsubrect(s,r,c,i,j);
					if(temp>max)
						max=temp;
				}
					a[i][j]=max;
					
		}
		max=a[0][0];
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				if(a[i][j]>max)
					max=a[i][j];
				printf("%d\n",max);
	return 1;
}

• 不能再短了,回去学动态规划咯! (720) eleapple 2005-10-10 01:19:41
  • I think you should learn "integral image" instead of DP (0) gongml 2005-10-10 06:18:22
    • Re:I think you should learn "integral image" instead of DP (0) eleapple 2005-10-10 17:13:44
      • Think you for your hint ,I conquer it under you help (16) eleapple 2005-10-10 17:18:51
        • Wow, so quickly... (0) gongml 2005-10-10 21:04:01