7-51 子矩阵(NOIP-2014-普及组-4) 分数 100 作者 严华云 单位 湖州师范学院 题目.png 输入格式: 第一行包含用空格隔开的四个整数n,m,r,c,意义如问题描述中所述,每两个整数之间用一个空格隔开。 接下来的n行,每行包含m个用空格隔开的整数,用来表示问题描述中那个n行m列的矩阵。 输出格式: 输出共1行,包含1个整数,表示满足题目描述的子矩阵的最小分值。 输入样例: 5 5 2 3 9 3 3 3 9 9 4 8 7 4 1 7 4 6 6 6 8 5 6 9 7 4 5 6 1 输出样例: 6 【输入输出样例 1 说明】 该矩阵中分值最小的2行3列的子矩阵由原矩阵的第4行、第5行与第1列、第3列、第4列交叉位置的元素组成,为 21.png ,其分值为|6-5|+|5-6|+|7-5|+|5-6|+|6-7|+|5-5|+|6-6|=6。 【数据说明】 对于50%的数据,1≤n≤12,1≤m≤12, 矩阵中的每个元素1≤a[i][j]≤20; 对于100%的数据,1≤n≤16,1≤m≤16,矩阵中的每个元素1≤a[i][j]≤1000,1≤r≤n,1≤c≤m。
时间: 2024-04-02 20:32:42 浏览: 32
首先,我们可以暴力枚举所有可能的子矩阵,并计算它们的分值,最后选出分值最小的一个。具体来说,对于每个子矩阵,我们可以先计算出它的每个元素与它所在行和列的中位数之差的绝对值,然后将这些绝对值相加即可得到该子矩阵的分值。时间复杂度为 $O(n^6)$,无法通过本题。
注意到题目中给定了 $r$ 和 $c$,因此我们可以通过预处理每个元素所在行和列的中位数,将每个元素与其所在行和列的中位数之差的绝对值预处理出来,从而将计算子矩阵分值的时间复杂度优化到 $O(n^4)$。具体来说,我们可以使用前缀和的思想,先预处理出每一行和每一列的前缀和,然后对于每个元素,可以通过前缀和求出它所在行和列的中位数,从而计算出它与它所在行和列的中位数之差的绝对值。时间复杂度为 $O(n^2)$。
接下来,我们考虑如何高效地枚举所有可能的子矩阵。我们可以枚举子矩阵的左边界和右边界,然后利用前缀和快速计算出该子矩阵内每一行的和以及每一列的和,从而在 $O(n)$ 的时间内计算出该子矩阵的和。具体来说,我们可以使用前缀和的思想,先预处理出每一行和每一列的前缀和,然后对于每个子矩阵,可以通过前缀和求出该子矩阵内每一行的和以及每一列的和,从而计算出该子矩阵的和。时间复杂度为 $O(n^4)$。
综上所述,总时间复杂度为 $O(n^4)$,可以通过本题。具体实现时,可以先预处理出每个元素与其所在行和列的中位数之差的绝对值,然后再枚举子矩阵的左边界和右边界,利用前缀和计算出该子矩阵的和并更新答案。
相关问题
c++写7-51 子矩阵(NOIP-2014-普及组-4) 分数 100 作者 严华云 单位 湖州师范学院 题目.png 输入格式: 第一行包含用空格隔开的四个整数n,m,r,c,意义如问题描述中所述,每两个整数之间用一个空格隔开。 接下来的n行,每行包含m个用空格隔开的整数,用来表示问题描述中那个n行m列的矩阵。 输出格式: 输出共1行,包含1个整数,表示满足题目描述的子矩阵的最小分值。 输入样例: 5 5 2 3 9 3 3 3 9 9 4 8 7 4 1 7 4 6 6 6 8 5 6 9 7 4 5 6 1 输出样例: 6 【输入输出样例 1 说明】 该矩阵中分值最小的2行3列的子矩阵由原矩阵的第4行、第5行与第1列、第3列、第4列交叉位置的元素组成,为 21.png ,其分值为|6-5|+|5-6|+|7-5|+|5-6|+|6-7|+|5-5|+|6-6|=6。 【数据说明】 对于50%的数据,1≤n≤12,1≤m≤12, 矩阵中的每个元素1≤a[i][j]≤20; 对于100%的数据,1≤n≤16,1≤m≤16,矩阵中的每个元素1≤a[i][j]≤1000,1≤r≤n,1≤c≤m。
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
int n, m, r, c;
int a[N][N], row_median[N][N], col_median[N][N], abs_diff[N][N][N][N];
void init() // 预处理每个元素与其所在行和列的中位数之差的绝对值
{
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
int row_sum = 0, cnt = 0;
for (int k = j; k <= j + c - 1 && k <= m; k ++ ) // 求该元素所在行的和
{
row_sum += a[i][k];
cnt ++ ;
}
int row_avg = (row_sum + cnt - 1) / cnt; // 求该元素所在行的平均数
row_median[i][j] = row_avg; // 该元素所在行的中位数
}
for (int j = 1; j <= m; j ++ )
for (int i = 1; i <= n; i ++ )
{
int col_sum = 0, cnt = 0;
for (int k = i; k <= i + r - 1 && k <= n; k ++ ) // 求该元素所在列的和
{
col_sum += a[k][j];
cnt ++ ;
}
int col_avg = (col_sum + cnt - 1) / cnt; // 求该元素所在列的平均数
col_median[i][j] = col_avg; // 该元素所在列的中位数
}
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
for (int x = i; x <= i + r - 1 && x <= n; x ++ )
for (int y = j; y <= j + c - 1 && y <= m; y ++ )
abs_diff[i][j][x][y] = abs(a[x][y] - row_median[i][j]) + abs(a[x][y] - col_median[x][y]); // 该元素与其所在行和列的中位数之差的绝对值
}
int calc(int lx, int ly, int rx, int ry) // 计算子矩阵的分值
{
int res = 0;
for (int i = lx; i <= rx; i ++ ) // 计算每一行的和
res += col_median[i][ly] * (ry - ly + 1) - col_median[i][ly] * (ry - ly) / 2 + col_median[i][ry] * (ry - ly + 1) - col_median[i][ry] * (ry - ly) / 2;
for (int j = ly; j <= ry; j ++ ) // 计算每一列的和
res += row_median[lx][j] * (rx - lx + 1) - row_median[lx][j] * (rx - lx) / 2 + row_median[rx][j] * (rx - lx + 1) - row_median[rx][j] * (rx - lx) / 2;
for (int i = lx; i <= rx; i ++ )
for (int j = ly; j <= ry; j ++ )
res += abs_diff[lx][ly][i][j]; // 计算该子矩阵内每个元素与其所在行和列的中位数之差的绝对值之和
return res;
}
int main()
{
cin >> n >> m >> r >> c;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
cin >> a[i][j];
init(); // 预处理每个元素与其所在行和列的中位数之差的绝对值
int res = 0x3f3f3f3f;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
for (int x = i; x <= n; x ++ )
for (int y = j; y <= m; y ++ )
if (x - i + 1 >= r && y - j + 1 >= c) // 子矩阵大小满足要求
res = min(res, calc(i, j, x, y)); // 更新答案
cout << res << endl;
return 0;
}
```
求一个m*n的矩阵的最大子矩阵和。 比如在如下这个矩阵中: 0 -2 -7 0 9 2 -6 2 -4
要求一个m*n的矩阵的最大子矩阵和,可以通过动态规划算法来解决。
首先,定义一个辅助矩阵dp,其中dp[i][j]表示以矩阵中第i行和第j列为右下角的子矩阵的最大和。然后从左上角开始遍历矩阵,对于每个位置(i, j),计算以该位置为右下角的子矩阵的最大和,并更新dp[i][j]的值。
具体的动态规划转移方程为:
dp[i][j] = max(dp[i-1][j] + matrix[i][j], dp[i][j-1] + matrix[i][j], matrix[i][j])
其中,matrix[i][j]表示原始矩阵中第i行和第j列的元素值。
遍历完整个矩阵后,dp矩阵中的最大值即为原始矩阵的最大子矩阵和。
例如,对于给定的矩阵:
0 -2 -7
0 9 2
-6 2 -4
经过动态规划后,得到的dp矩阵为:
0 -2 -7
0 9 2
-6 8 1
dp矩阵中最大值为9,即原始矩阵中的最大子矩阵和为9。
因此,可以通过动态规划算法来高效求解一个m*n矩阵的最大子矩阵和。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)