首页 > 代码库 > HDU 1081 DP找最大和的矩阵

HDU 1081 DP找最大和的矩阵

题目大意:

在一个给定的大矩阵中找一个小型的矩阵,使这个矩阵中的元素和最大

 

可以先来看下面这个问题:

  原来有做过在一个给定的数字序列中找一个最大和子序列,核心代码如下:

   

 1         int _max = num[0]; 2         int sum = num[0]; 3         int st = 0; 4         int la = 0; 5         int rec; 6         for(int i = 1 ; i<k ; i++){ 7             if(sum < 0){ 8                 rec = i;//记录起点 9                 sum = 0;10             }11             sum += num[i];12             if(sum > _max){13                 _max = sum;14                 st = rec;15                 la = i;16             }17         }

当然如果只是求最大值,可以不用st , la,这是用来记录找到的序列的端点位置的

明显这个问题和找最大和矩阵有着共通点,这个找子序列可以看作是一维的,而找矩阵,矩阵上的点也是相互紧连的,那也就是可以看作是在二维的平面上找

这里需要把一维的转化为二维的是关键

 

我们可以假定把每一行看作单个的元素,知道每个元素的值,那我们就能够将n列,看作有n个这样的压缩元素,那我们就是在这n个元素中找最大值

(当然压缩列也是可以的,这里我的代码写的是压缩行)

 

我们需要找到所有情况,因为所求矩阵不一定端点就在大矩阵的两端,也可以是中间,这里N <= 100 , N表示边, 那么上面的点至少有101个 , 所以我们

至少需要对每一行有101*101个这样的压缩情况,另外我们需要知道每一行压缩101*101种情况后的值那么至少要101*101*100的空间来保存

显然不太合理,当然我本人没试过,按理觉得也不会MLE

那么我们转化成用二维的sum[i][j]保存,表示第i行前j个数的和

那么比如我们得到第k行压缩第5个点和第99个点中间得到的大小为94的矩阵长度为一个元素

那么它的值就为 sum[k][99] - sum[k][5]

 

压缩好后就是简单的在线性时间内解决最大和子序列的问题了

 1 #include <cstdio> 2 #include <cstring> 3  4 using namespace std; 5 const int N = 105; 6 int num[N][N] , sum[N][N]; 7  8 int main() 9 {10   //  freopen("a.in" , "r" , stdin);11     int n , maxn;12     while(~scanf("%d" , &n)){13         memset(sum , 0 , sizeof(sum));14 15         for(int i = 0 ; i<n ; i++)16             for(int j = 0 ; j<n ; j++){17                 scanf("%d" , &num[i][j]);18                 sum[i][j+1] = num[i][j] + sum[i][j];19             }20 21         maxn = 0;22         for(int i = 0 ; i<=n ; i++)23             for(int j = 0 ; j<i ; j++)24             {25                 int suma = 0;26                 for(int k = 0 ; k<n ; k++)//从第i行不断往下在i到j列找到某一段矩阵得到最大值27                 {28                     if(suma<0)29                         suma = 0;30 31                     suma += (sum[k][i] - sum[k][j]);32                     if(suma > maxn)33                         maxn = suma;34                 }35             }36 37         printf("%d\n" , maxn);38     }39     return 0;40 }

 

HDU 1081 DP找最大和的矩阵