动态规划解题报告:To the Max

题目名称:To the Max

题目来源:POJ 1050

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1050

题目分类:动态规划

解题思路:

题目要求清晰,求出最大子矩阵。其中,输入数据是一个N*N的矩阵。

(1)化简为一维情况

    矩阵是二维的,先把这个问题简化,如果变成一维的情况如何?即对于形如 1 -2 3 4 7 的这一行求最大子段问题,对于这个一维情况,容易知道如下的规律:
   

    若记b[j]为从a[i]到a[j]的最大的子段和(j是定的,“最大”指的是i从1到j-1中,a[i]+...+a[j]最大的),那么所求的max{ a[i]+a[i+1]+...+a[j-1]+a[j] (1<=i<j<=n) }=max{ max{ a[i]+..+a[j] (1<=j<=n) } }=max{ b[1]+...+b[n] }。

b[]由定义可知:j==1时,b[1]=a[1];j>1时,b[j]=max{ b[j-1]+a[j],a[j] }。

实际上,这个一维情况可以继续化简,即b[j] = (b[j-1]>0?b[j-1]:0)+a[j]

(2)从一维到二维

    一维的情况很简单,如何把一维的情况转化为二维情况呢?

例如,对于本题的测试数据:

我们可以每次任选几行,压缩成一行,这样就转化为了一维情况。

例如,我们求1~2行中的最大子矩阵:即矩阵高为2(1~2行),宽为1:4的矩阵,可以先把1~2行相加,得到9 0 -13 2,再求这个单行的最大子段,由此就可以求得1~2行的最大子矩阵。

依次类推,我们需要求得所有的高为1、2、3、4的矩阵,即

高为1的:

0 -2 -7 0   和 9   2 -6   2 和 -4 1 -4 1 和 -1 8 0 -2

高为2的:1~2行,2~3行 3~4行

。。。。。

因为这是一个Cn的组合问题,所以我们可以设置两个变量i,j,每次选择从i到j的行,压缩成一行,然后求这一行的最大字段。其中,i,j为两层循环分别为从1~N

(3)程序

#include <iostream>
using namespace std;

int rect[101][101];

int maxvalue;

//思想:先压缩到一行,然后横向DP
//横向DP 递推公式 maxn[i]=max{0,maxn[i-1]}+a[i];
void dp(int n)
{
int line[101];//压缩到一行的数据

for(int i=1;i<=n;i++)
{
   for(int j=1;j<=n;j++)
   {

    //把第i到j行压缩成一行
    memset(line,0,sizeof(line));
    for(int row = i;row<=j;row++)
    {

     for(int col = 1;col<=n;col++)
     {
      line[col]+=rect[row][col];
     }
    }//end 把第i到j行压缩成一行
   
    //至此,line[1:n]变成了一维的最长子序列
    for(int i=2;i<=n;i++)
    {
     line[i] = (line[i-1]>0?line[i-1]:0)+line[i];

     if(line[i]>maxvalue)
     {
      maxvalue = line[i];
     }
    }

   }//end for j
}//end for i

}

int main()
{
int n;

while(cin>>n)
{
   //数据输入
   for(int i=1;i<=n;i++)
   {
    for(int j=1;j<=n;j++)
    {
     cin>>rect[i][j];
    }
   }
  
   maxvalue = 0;
   dp(n);
  
   cout<<maxvalue<<endl;
}

return 0;

}

Leave a Reply

Your email address will not be published. Required fields are marked *