【解题报告】[动态规划] RQNOJ PID106 / 最大加权矩形

 1 #include<stdio.h>
 2 int a[105][105];
 3 int dp[105][105];
 4 int s[105];
 5 int dp2[105];
 6 int n;
 7 int Max(int a, int b)
 8 {
 9     return a>b?a:b;
10 }
11 int main()
12 {
13     int ans=0,i,j,ii;
14     scanf("%d",&n);
15     for(i=0;i<n;i++)
16     {
17         for(j=0;j<n;j++)
18         {
19             scanf("%d",&a[i][j]);
20         }
21     }
22     for(i=0;i<n;i++)
23     {
24         for(j=0;j<n;j++) s[j]=0;
25         for(ii=i;ii<n;ii++)
26         {
27             for(j=0;j<n;j++)
28             {
29                 s[j]+=a[ii][j];
30                 if(j==0) dp2[j]=s[j];
31                 else dp2[j]=Max(dp2[j-1]+s[j],s[j]);
32                 dp[ii][j]=Max(dp[ii][j],dp2[j]);
33                 ans=Max(dp[ii][j],ans);
34             }
35         }
36     }
37     printf("%d\n",ans);
38     return 0;
39 }