题面

思路:分析公式,我们可以发现平均值那一项和我们怎么分的具体方案无关,影响答案的是每个矩阵的矩阵和的平方,由于数据很小,我们可以预处理出每个矩阵的和的平方,执行状态转移。

设dp[l1][r1][l2][r2][k]是矩阵l1,r1,l2,r2切割k次的最小值,我们可以枚举是横着切还是竖着切执行状态转移。

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std; int dp[10][10][10][10][16], sum[10][10][10][10];
bool v[10][10][10][10][16];
int a[10][10]; void init() {
for (int l1 = 1; l1 <= 8; l1++)
for (int r1 = 1; r1 <= 8; r1++)
for (int l2 = l1; l2 <= 8; l2++)
for (int r2 = r1; r2 <= 8; r2++) {
int ans = 0;
for (int i = l1; i <= l2; i++)
for (int j = r1; j <= r2; j++) {
ans += a[i][j];
}
sum[l1][r1][l2][r2] = ans * ans;
}
} int solve(int l1, int r1, int l2, int r2, int k) {
if (v[l1][r1][l2][r2][k]) return dp[l1][r1][l2][r2][k];
if (k == 1) {
return dp[l1][r1][l2][r2][k] = sum[l1][r1][l2][r2];
}
int ans = INF;
for (int i = l1; i < l2; i++) {
ans = min(ans, min(solve(l1, r1, i, r2, k - 1) + sum[i + 1][r1][l2][r2], solve(i + 1, r1, l2, r2, k - 1) + sum[l1][r1][i][r2]));
}
for (int i = r1; i < r2; i++) {
ans = min(ans, min(solve(l1, r1, l2, i, k - 1) + sum[l1][i + 1][l2][r2], solve(l1, i + 1, l2, r2, k - 1) + sum[l1][r1][l2][i]));
}
v[l1][r1][l2][r2][k] = 1;
return dp[l1][r1][l2][r2][k] = ans;
}
int main() {
int n, tot = 0;
scanf("%d", &n);
for (int i = 1; i <= 8; i ++) {
for (int j = 1; j <= 8 ; j++) {
scanf("%d", &a[i][j]);
tot += a[i][j];
}
}
init();
solve(1, 1, 8, 8, n);
double ans = sqrt(dp[1][1][8][8][n] * 1.0 / n - (tot * 1.0 / n) * (tot * 1.0 / n));
printf("%.3f\n", ans);
}

  

最新文章

  1. 【JUC】JUC线程池框架综述
  2. PL/SQL异常处理
  3. Delphi编译的程序,查看控件名称方法
  4. Windows Phone 8.1商店启动协议
  5. 如何通过PowerShell在Visual Studio的Post-build中预热SharePoint站点
  6. log4j.properties详解与例子
  7. Github开源编辑器Atom
  8. java代码实现自动登录功能
  9. 在MacOS中,Unity使用VSCode开发,4.7版本无法正常使用C#
  10. strcpy函数
  11. Mysql 了解changeBuffer 与 purge 调优
  12. C# 生成海报,文本区域指定和换行,图片合成
  13. Exp6 信息搜集与漏洞扫描 20164313 杜桂鑫
  14. git 入门教程之1分钟快速了解 git
  15. CentOS 7下安装Python3.5
  16. vijos 1006 晴天小猪历险记之Hill——数字三角形的终极变化
  17. ExpandoObject与DynamicObject的使用 RabbitMQ与.net core(一)安装 RabbitMQ与.net core(二)Producer与Exchange ASP.NET Core 2.1 : 十五.图解路由(2.1 or earler) .NET Core中的一个接口多种实现的依赖注入与动态选择看这篇就够了
  18. sigar在Centos和Windows下使用java系统软硬件配置信息
  19. Android Sms短信发送
  20. 基于BeanNameViewResolver解析器,自定义视图

热门文章

  1. Shiro安全配置
  2. 201621123014《Java程序设计》第六周学习总结
  3. localtime 和 localtime_r 的区别
  4. Android源代码因删除所有git仓库导致的编译错误
  5. 【LeetCode】008. String to Integer (atoi)
  6. C#中将dateTimePicker初始值设置为空
  7. Js中获取键盘的事件
  8. php 服务器的安全笔记
  9. 预备架构的工具ADMEMS矩阵
  10. linux内核图形配置疑难解决