[AcWing 321] 棋盘分割
2022/7/9 23:20:25
本文主要是介绍[AcWing 321] 棋盘分割,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
点击查看代码
#include<iostream> #include<cstring> #include<cmath> using namespace std; typedef long long LL; const int N = 10, M = 20; const double INF = 1e9; int n, m = 8; int s[N][N]; double f[N][N][N][N][M]; double xx; int front_sum(int x1, int y1, int x2, int y2) { return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]; } double get(int x1, int y1, int x2, int y2) { double sum = front_sum(x1, y1, x2, y2) - xx; return sum * sum / n; } double dp(int x1, int y1, int x2, int y2, int k) { double &v = f[x1][y1][x2][y2][k]; if (v >= 0) return v; if (k == 1) return v = get(x1, y1, x2, y2); v = INF; for (int i = x1; i < x2; i ++) { v = min(v, dp(x1, y1, i, y2, k - 1) + get(i + 1, y1, x2, y2)); v = min(v, dp(i + 1, y1, x2, y2, k - 1) + get(x1, y1, i, y2)); } for (int i = y1; i < y2; i ++) { v = min(v, dp(x1, y1, x2, i, k - 1) + get(x1, i + 1, x2, y2)); v = min(v, dp(x1, i + 1, x2, y2, k - 1) + get(x1, y1, x2, i)); } return v; } int main() { cin >> n; for (int i = 1; i <= m; i ++) for (int j = 1; j <= m; j ++) { cin >> s[i][j]; s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; } xx = (double)s[m][m] / n; memset(f, -1, sizeof f); printf("%.3f\n", sqrt(dp(1, 1, 8, 8, n))); return 0; }
- 状态表示
\(f[x_1][y_1][x_2][y_2][k]\) 表示所有将矩阵 \((x_1, y_1),(x_2, y_2)\) 分割为 \(k\) 份的均方差的平方的最小值 - 状态计算
考虑将矩阵 \((x_1, y_1),(x_2, y_2)\) 分割为 \(2\) 份的情况,也就是在矩阵中划一条分割线,将矩阵分为两部分,考虑分割线水平和分割线竖直分两种情况:
① 分割线水平,分割线位置的取值为 \(\lambda \ \epsilon \ [y_1, y_2)\),划分为 \([x_1, y_1, x_2, \lambda]\) 和 \([x_1, \lambda + 1, x_2, y_2]\) 两部分
① 分割线竖直,分割线位置的取值为 \(\lambda \ \epsilon \ [x_1, x_2)\),划分为 \([x_1, y_1, \lambda, y_2]\) 和 \([\lambda + 1, y1, x_2, y_2]\) 两部分
这篇关于[AcWing 321] 棋盘分割的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!