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

原题地址：http://www.rqnoj.cn/problem/106

解题思路：

　　一维的情况下求最大字串和的状态转移方程是：s[i]=max{s[i-1]+a[i],a[i]}

　　二维的情况下，只要将第i行到第ii行的每列数字加起来，再用一维的方法计算就可以了。遍历i和ii的所有情况即可。复杂度O（n^3）

代码：

 #include<stdio.h>

 int a[][];

 int dp[][];

 int s[];

 int dp2[];

 int n;

 int Max(int a, int b)

 {

     return a>b?a:b;

 }

 int main()

 {

     int ans=,i,j,ii;

     scanf("%d",&n);

     for(i=;i<n;i++)

     {

         for(j=;j<n;j++)

         {

             scanf("%d",&a[i][j]);

         }

     }

     for(i=;i<n;i++)

     {

         for(j=;j<n;j++) s[j]=;

         for(ii=i;ii<n;ii++)

         {

             for(j=;j<n;j++)

             {

                 s[j]+=a[ii][j];

                 if(j==) dp2[j]=s[j];

                 else dp2[j]=Max(dp2[j-]+s[j],s[j]);

                 dp[ii][j]=Max(dp[ii][j],dp2[j]);

                 ans=Max(dp[ii][j],ans);

             }

         }

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

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

最新文章

热门文章