poj2106，poj 1050(DP)

2023-09-20 阅读 22 评论 0

摘要：最大子矩阵和。类似于子序列最大和。 1 // File Name: 1050.cpp 2 // Author: Missa_Chen 3 // Created Time: 2013年06月22日星期六 17时06分39秒 4 5 #include <iostream> 6 #include <string> 7 #include <algorithm> 8 #include <cstdio> 9 #inc

最大子矩阵和。类似于子序列最大和。

 1 // File Name: 1050.cpp
 2 // Author: Missa_Chen
 3 // Created Time: 2013年06月22日 星期六 17时06分39秒
 4 
 5 #include <iostream>
 6 #include <string>
 7 #include <algorithm>
 8 #include <cstdio>
 9 #include <cstring>
10 #include <cmath>
11 #include <queue>
12 #include <map>
13 #include <stack>
14 #include <set>
15 #include <cstdlib>
16 
17 using namespace std;
18 
19 #define LL long long
20 const int inf = 0x3f3f3f3f;
21 const int maxn = 101;
22 int n;
23 int sum[maxn][maxn];
24 int main()
25 {
26     while (~scanf("%d",&n))
27     {
28         for (int i = 1; i <= n; ++i)
29             for (int j = 1; j <= n; ++j)
30                 scanf("%d", &sum[i][j]);
31         for (int i = 1; i <= n; ++i)
32             sum[i][0] = 0;
33         for (int i = 1; i <= n; ++i)
34             for (int j = 2; j <= n; ++j)
35                 sum[i][j] += sum[i][j - 1];
36         int ans = -inf;
37         for (int i = 1; i <= n; ++i)
38             for (int j = i; j <= n; ++j)
39             {
40                 int tmp = -inf;
41                 for (int k = 1; k <= n; ++k)
42                 {
43                     if (tmp >= 0)
44                         tmp += (sum[k][j] - sum[k][i - 1]);
45                     else
46                         tmp = sum[k][j] - sum[k][i - 1];
47                     ans = max(ans, tmp);
48                 }
49             }
50         printf("%d\n", ans);
51     }
52     return 0;
53 }