1 //Accepted    200 KB    16 ms 2 //dp 3 //类比一维的情况 4 //枚举i和j（i<=j），可以通过预处理在O(1)的时间求出a[k][i],a[k][i+1],...a[k][j]的和 5 //然后就是纵向类比一维的情况 6 #include <cstdio> 7 #include <cstring> 8 #include <iostream> 9 using namespace std;10 const int imax_n = 105;11 int a[imax_n][imax_n];12 int d[imax_n];13 int n;14 int max(int a,int b)15 {16     return a>b?a:b;17 }18 void Dp()19 {20     for (int i=1;i<=n;i++)21     {22         for (int j=1;j<=n;j++)23         a[i][j]+=a[i][j-1];24     }25     int ans=-1000000;26     for (int i=1;i<=n;i++)27     {28         for (int j=i;j<=n;j++)29         {30             memset(d,0,sizeof(d));31             d[1]=a[1][j]-a[1][i-1];32             for (int k=2;k<=n;k++)33             {34                 d[k]=max(d[k-1]+a[k][j]-a[k][i-1],a[k][j]-a[k][i-1]);35                 ans=max(d[k],ans);36             }37         }38     }39     printf("%d\n",ans);40 }41 int main()42 {43     while (scanf("%d",&n)!=EOF)44     {45         for (int i=1;i<=n;i++)46         {47             for (int j=1;j<=n;j++)48             scanf("%d",&a[i][j]);49         }50         Dp();51     }52     return 0;53 }

 1 //Accepted    244 KB    79 ms 2 //枚举 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7 const int imax_n = 105; 8 int a[imax_n][imax_n]; 9 int sum[imax_n][imax_n];10 int n;11 void slove()12 {13     memset(sum,0,sizeof(sum));14     for (int i=1;i<=n;i++)15     for (int j=1;j<=n;j++)16     sum[i][j]=a[i][j]+sum[i][j-1];17     for (int i=1;i<=n;i++)18     for (int j=1;j<=n;j++)19     sum[i][j]+=sum[i-1][j];20     int ans=-10000;21     for (int i=1;i<=n;i++)22     for (int j=1;j<=n;j++)23     {24         for (int k=i;k<=n;k++)25         for (int l=j;l<=n;l++)26         {27             int temp=sum[k][l]-sum[i-1][l]-sum[k][j-1]+sum[i-1][j-1];28             if (temp>ans) ans=temp;29         }30     }31     printf("%d\n",ans);32 }33 int main()34 {35     while (scanf("%d",&n)!=EOF)36     {37         for (int i=1;i<=n;i++)38         for (int j=1;j<=n;j++)39         scanf("%d",&a[i][j]);40         slove();41     }42     return 0;43 }