洛谷 P2258 子矩阵
2022/8/8 23:23:05
本文主要是介绍洛谷 P2258 子矩阵,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言
那个 Atcoder Beginner 263 的 E 还真是恶心……
呃,我什么也没说,我什么也没说……
正文
题意
有个 $ n \times m $ 的矩阵,从里面选 $ r $ 行 $ c $ 列出来。
问这 $ r $ 行 $ c $ 列的交叉点“相邻元素的差”的和最少为多少。
$ 60 pts $
思路
直接暴力枚举。
先枚举 $ r $,再枚举 $ c $。
时间复杂度:$ O(C _{n} ^ {r} C _{m} ^{c} rc) $
空间复杂度:$ O(r + c) $
代码
代码就不放了,谁都会写。
$ 100 pts $
思路
是不是有很多人觉得满分根本不用枚举,$ O(n^k) $ 的暴力就搞定了?
我告诉你们吧,正解还是要枚举的……
先选出 $ r $ 行来,然后再来 $ DP $。
定义 $ f_{i, j} $ 为前 $ i $ 列选 $ j $ 列,第 $ i $ 列必须选,和最小为多少。
容易得到 $ f_{i, j} = f_{k, j - 1} + sg_{i} + tc_{k, i} (j - 1 \le k \lt i)$,其中 $ sg_{i} $ 为单单第 $ i $ 列的差之和(single),而 $ tc_{i, j} $ 为单单第 $ i $ 列与第 $ j $ 列横向的差之和(two columns)。
好了,天真的我以为这样就结束了。
然而……
- 随时都 $ DP $:
- $ DFS $
- 暴力处理 $ sg, tc $
- $ DP $
- 边界有两个:
- $ f_{i, 1} = sg_{i} $。只选一列,第 $ i $ 列还必须选,你不选谁选。
- $ f_{i, i} = f_{i - 1, i - 1} + sg_{i} + tc_{i - 1, i} $。全部选了,这列自己算一下,和前一列也算一下,多层递推得出答案。
- 循环要注意:
- $ DFS $ 用 $ r $ 层,循环那一列时是 $ m $ 。
- $ tc $ 的 $ i, j $ 是 $ m $,枚举行 $ k $ 时是 $ r $。
- 最后在状态转移方程里的 $ k $ 是 $ [j - 1, i) $。
总之,我想到的用山峰的高度表示是:
1 2 3 5 7 8 10 (一路顺风)
实际上的是:
1 100 1 100 1 100 1 (坎坷不平)
AZ……
时间复杂度:$ O(C _{n} ^{r} m^{2}) $
空间复杂度:$ O(m^{2}) $
代码
#include <bits/stdc++.h> using namespace std; int a[20][20]; int choose[20]; int f[20][20]; int ans = 0x3f3f3f3f; int n, m, r, c; int yyy_2013_OI[20], yyy_2013_Math[20][20]; void brute_force() { for (int j = 1; j <= m; j++) { yyy_2013_OI[j] = 0; for (int i = 1; i <= r - 1; i++) { yyy_2013_OI[j] += abs(a[choose[i]][j] - a[choose[i + 1]][j]); } } for (int i = 1; i <= m; i++) { for (int j = i + 1; j <= m; j++) { yyy_2013_Math[i][j] = 0; for (int k = 1; k <= r; k++) { yyy_2013_Math[i][j] += abs(a[choose[k]][i] - a[choose[k]][j]); } } } } void dp() { for (int i = 1; i <= m; i++) { for (int j = 1; j <= min(i, c); j++) { if (j == 1) { f[i][j] = yyy_2013_OI[i]; } else if (j == i) { f[i][j] = f[i - 1][j - 1] + yyy_2013_OI[i] + yyy_2013_Math[i - 1][i]; } else { f[i][j] = 0x3f3f3f3f; for (int k = j - 1; k <= i - 1; k++) { f[i][j] = min(f[i][j], f[k][j - 1] + yyy_2013_OI[i] + yyy_2013_Math[k][i]); } } if (j == c) { ans = min(ans, f[i][c]); } } } } void dfs(int lvl) { if (lvl == r + 1) { brute_force(); dp(); return; } for (int i = choose[lvl - 1] + 1; i <= n; i++) { choose[lvl] = i; dfs(lvl + 1); choose[lvl] = 0; } } int main() { scanf("%d %d %d %d", &n, &m, &r, &c); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &a[i][j]); } } dfs(1); printf("%d", ans); return 0; }
感谢你能看到这儿,来一个推荐吧!!!
这篇关于洛谷 P2258 子矩阵的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行