首页 > 代码库 > [BZOJ 1048] [HAOI2007] 分割矩阵 【记忆化搜索】
[BZOJ 1048] [HAOI2007] 分割矩阵 【记忆化搜索】
题目链接：BZOJ - 1048
题目分析
感觉这种分割矩阵之类的题目很多都是这样子的。
方差中用到的平均数是可以直接算出来的，然后记忆化搜索 Solve(x, xx, y, yy, k) 表示横坐标范围 [x, xx]， 纵坐标范围 [y, yy] 的矩阵切成 k 块的最小 sigma((Vi - Ave)^2) 。
然后再递归将矩阵分得更小，直到 k 为 1 的时候直接返回相应的值。
代码
#include <iostream>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>#include <cstdio>using namespace std;const int MaxN = 15 + 5, MaxT = 15 + 5;int n, m, t, Num;int Sum[MaxN][MaxN];typedef double DB;const DB INF = 999999999;DB Ave;DB f[MaxN][MaxN][MaxN][MaxN][MaxT];DB Get(int x, int y, int xx, int yy) { return (DB)(Sum[xx][yy] - Sum[x - 1][yy] - Sum[xx][y - 1] + Sum[x - 1][y - 1]);}inline DB Sqr(DB x) {return x * x;} inline DB gmin(DB a, DB b) {return a < b ? a : b;}DB Solve(int x, int xx, int y, int yy, int k) { if (f[x][xx][y][yy][k] != -1) return f[x][xx][y][yy][k]; if (k == 1) return f[x][xx][y][yy][k] = Sqr(Get(x, y, xx, yy) - Ave); DB ret = INF; for (int i = x; i <= xx - 1; ++i) for (int j = 1; j <= k - 1; ++j) ret = gmin(ret, Solve(x, i, y, yy, j) + Solve(i + 1, xx, y, yy, k - j)); for (int i = y; i <= yy - 1; ++i) for (int j = 1; j <= k - 1; ++j) ret = gmin(ret, Solve(x, xx, y, i, j) + Solve(x, xx, i + 1, yy, k - j)); return f[x][xx][y][yy][k] = ret; }int main() { scanf("%d%d%d", &n, &m, &t); for (int i = 1; i <= n; ++i) for (int j = i; j <= n; ++j) for (int p = 1; p <= m; ++p) for (int q = p; q <= m; ++q) for (int o = 1; o <= t; ++o) f[i][j][p][q][o] = -1; memset(Sum, 0, sizeof(Sum)); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { scanf("%d", &Num); Sum[i][j] = Sum[i][j - 1] + Sum[i - 1][j] - Sum[i - 1][j - 1] + Num; } } Ave = (DB)Sum[n][m] / (DB)t; Solve(1, n, 1, m, t); printf("%.2lf\n", sqrt(f[1][n][1][m][t] / t)); return 0;}
[BZOJ 1048] [HAOI2007] 分割矩阵 【记忆化搜索】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。