学步园

UVA_10827

    由于矩形上下左右是相接的，所以我们不妨先在图的右、下、右下分别补上三个完整矩形，然后枚举矩形的左上角位置。由于数据量比较大，所以我们需要不断利用已经计算过的结果，这也是动态规划的基本思想之一。

#include<stdio.h>
#include<string.h>
int a[200][200],b[200],c[200];
int main()
{
int i,j,k,t,n,x,y,ans;
    scanf("%d",&t);
while(t--)
    {
        scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
            {
                scanf("%d",&a[i][j]);
                a[i+n][j]=a[i][j+n]=a[i+n][j+n]=a[i][j];
            }
        ans=-1000000000;
for(x=0;x<n;x++)
for(y=0;y<n;y++)
for(j=0;j<n;j++)
for(i=0;i<n;i++)
                    {
                        c[i]=a[i+x][j+y];
if(i)
                            c[i]+=c[i-1];
if(j)
                            b[i]+=c[i];
else
                            b[i]=c[i];
if(b[i]>ans)
                            ans=b[i];
                    }
        printf("%d\n",ans);
    }
return 0;    
}