首页 > 代码库 > HDU 1081 To The Max

HDU 1081 To The Max

2024-07-14 06:55:52   224人阅读

求子矩阵的最大和

对于样例：

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

其最大子矩阵为

9 2
-4 1
-1 8

这个子矩阵的和为15

 

想明白后，这是个最大连续子序列的变形

sum[k]存放的是矩阵中第k列从第i行到第j行的和

每次求出sum数组的最大连续子序列，就是求得第i行到第j行的最大子矩阵

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 int dp[105], sum[105]; 8 int data[105][105]; 9 10 int main(void)11 {12     #ifdef LOCAL13         freopen("1081in.txt", "r", stdin);14     #endif15 16     int n;17     while(scanf("%d", &n) == 1)18     {19         int i, j, k;20         int ans = -1000;21         for(i = 0; i < n; ++i)22             for(j = 0; j < n; ++j)23                 scanf("%d", &data[i][j]);24 25         for(i = 0; i < n; ++i)26         {27             memset(sum, 0, sizeof(sum));28             for(j = i; j < n; ++j)29             {30                 for(k = 0; k < n; ++k)31                     sum[k] += data[j][k];32                 dp[0] = sum[0];33                 for(k = 1; k < n; ++k)34                 {35                     if(dp[k - 1] > 0)36                         dp[k] = dp[k - 1] + sum[k];37                     else38                         dp[k] = sum[k];39                     if(dp[k] > ans)40                         ans = dp[k];41                 }42             }43         }44 45         printf("%d\n", ans);46     }47     return 0;48 }
代码君

 

小结：

这个算法里面还是有很多重复计算的部分，可以考虑将data[i][j]中存放矩阵中第j列前i行的和

再计算sum[k]的时候，

sum[k] = data[j][k] - data[i][k];

 

HDU 1081 To The Max


联系
我们