pku1050

转自

一道简单的动态规划题

#include <stdio.h>
#include <stdlib.h>
int G[101][101]={0};
int res1[101][101]={0};
int n;
int res=0;
int main(){
     int i,j,k,m;
     scanf("%d",&n);
     for(i=1;i<=n;i++){
     for(j=1;j<=n;j++){
     scanf("%d",&G[i][j]);
     res1[i][j]=res1[i][j-1]+G[i][j];
     }
     }
     for(i=1;i<=n;i++){
     for(j=1;j<=n;j++)
     res1[i][j]+=res1[i-1][j];
     }
     for(i=1;i<=n;i++){
     for(j=1;j<=n;j++){
     if(res1[i][j] > res) res = res1[i][j];
     for(k=0;k<=i;k++){
         for(m=0;m<=j;m++){
             if(k==i&&m==j) continue;
             int t=res1[i][j] - res1[k][j] - res1[i][m] + res1[k][m];
             if(t>res) res=t;
         }
     }
     }
     }
     printf("%d\n",res);
     return 0;
}