首页 > 其他分享 >题解:P2217 [HAOI2007] 分割矩阵

题解:P2217 [HAOI2007] 分割矩阵

时间:2024-12-06 22:10:49浏览次数:8  
标签:sy sx tx ty int 题解 HAOI2007 num P2217

思路

  • 首先,我们要弄明白题中的方差是什么。

    公式:$S = \sqrt{\frac{1}{n} \sum_{i=1}^{n} (x_i - \bar{x})^2}$

  • 接下来,我们思考一下题目怎么做。

    数据很小,于是想到了暴搜

    但是时间复杂度有点难以接受啊,优化一下吧。

    有一种很有效的优化,那就是广为人知的记忆化搜索。它能使所有重复的操作只做一次,大大降低了时间复杂度。

    下面我们来看看框架。

    用 $f[i][sx][tx][sy][ty]$ 表示分割 $i$ 次,操作范围为左上角在 $(sx,sy)$ 右下角在 $(tx,ty)$ 的矩阵得到 $\sum_{i=1}^{n} (x_i - \bar{x})^2$ 的最小值。很容易想到,dfs 函数的参数就也是这五个值了。

    那么函数出口是什么情况呢?

    $i=0$ 的时候返回矩阵里所有元素之和,我们可以用二维前缀和来预处理。

    函数内部呢?

    如果已经存过答案了,那么返回 $f[i][sx][tx][sy][ty]$ 。否则枚举切断的位置及两边分配的分割次数并递归求解。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const double INF = 1e300; // 初始值,极大值

int n, m, k;
int a[25][25];
double s[25][25], avg; // 二维前缀和,平均值
double f[25][25][25][25][25]; // 记忆化数组

double dfs(int num, int sx, int tx, int sy, int ty) // 递归函数
{
    if (sx > tx || sy > ty || num < 0) // 错误的情况
        return 0;
    if (f[num][sx][tx][sy][ty] != INF) // 如果存过了
        return f[num][sx][tx][sy][ty]; // 直接返回
    if (num == 0) // 出口
    {
        double sum = s[tx][ty] - s[sx - 1][ty] - s[tx][sy - 1] + s[sx - 1][sy - 1];
        sum = (sum - avg) * (sum - avg);
        return f[num][sx][tx][sy][ty] = sum;
    }
    for (int i = sx; i < tx; i++) // 分割位置
        for (int j = 0; j < num; j++) // 次数分配
            f[num][sx][tx][sy][ty] = min(f[num][sx][tx][sy][ty], dfs(j, sx, i, sy, ty) + dfs(num - j - 1, i + 1, tx, sy, ty));
    for (int i = sy; i < ty; i++) // 分割位置
        for (int j = 0; j < num; j++) // 次数分配
            f[num][sx][tx][sy][ty] = min(f[num][sx][tx][sy][ty], dfs(j, sx, tx, sy, i) + dfs(num - j - 1, sx, tx, i + 1, ty));
    return f[num][sx][tx][sy][ty]; 
}

int main()
{
    for (int i = 0; i <= 24; i++)
        for (int sx = 0; sx <= 24; sx++)
            for (int tx = 0; tx <= 24; tx++)
                for (int sy = 0; sy <= 24; sy++)
                    for (int ty = 0; ty <= 24; ty++)
                        f[i][sx][sy][tx][ty] = INF; // 初值
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; // 预处理
        }
    avg = s[n][m] / k; // 平均值
    double ans = sqrt(dfs(k - 1, 1, n, 1, m) / k);
    printf("%.2lf\n", ans); // 别忘了位数
    return 0;
}

标签:sy,sx,tx,ty,int,题解,HAOI2007,num,P2217
From: https://www.cnblogs.com/thrift/p/18591516

相关文章

  • 题解:AT_abc368_d[ABC368D] Minimum Steiner Tree
    题目大意题目给定一棵由$N$个节点组成的无根树,删除其中的一些点和边,使剩下的点和边仍然能够组成一棵树,且包含给定的$K$个特殊点,问最少剩下几个点。思路我们可以发现,这棵无根树的根必须是给定的特殊点之一,不然根节点就可以删除,答案就不是最优。所以我们使用深度优先搜索遍......
  • 题解:AT_abc368_c [ABC368C] Triple Attack
    思路$N$很大,导致$T$可能也会很大,所以一遍一遍的模拟就会超时。我们发现,题中有一个要求:每次必须打离自己最近的活着的敌人。我们就只用枚举每个敌人即可,在枚举的过程中计算答案。细节处理这道题有点难度,因为$T$是$3$的倍数时能量会变成$3$。这是个周期问题,自然会想到除......
  • CF2050G Tree Destruction 题解
    【题意简述】你有一棵树,你可以从里面删除一条链上的节点,问剩下的点的联通块数量最大是多少。【思路】一眼树形dp,默认根为\(1\)。我们以这棵树的\(1\)节点作为示例。设\(dp[i][0]\)表示\(i\)节点的子树中选一条链,\(i\)​不在链上的最大联通块数。设\(dp[i][1]\)......
  • CF2050F Maximum modulo equality 题解
    【题意简述】你有一个长度为\(n\)的数组\(a\)。每一次询问给定\(l,r\),寻找最大的\(m\)使得\(a_l\)到\(a_r\)的所有数对\(m\)同余,【前置数学芝士】首先是一个非常Naive的结论,请自行感性证明:设\(a>b\),\(a\)和\(b\)对\(a-b\)同余。理性证明:设\(p=a-b\),\(......
  • P5007 DDOSvoid 的疑惑 题解
    题目传送门思路树形dp模版题。设\(dp_i\)为\(pos\)的最优解,\(dp2_i\)为只考虑\(pos\)子树时,毒瘤集的数量。可得:\(dp_i=dp_{i}\timesdp2_{son}+dp_{son}\timesdp2_{i}+dp_i+dp_{son}\)\(dp2_i=dp2_{i}\timesdp2_{son}+dp2_{i}+dp2_{son}\)用深搜来更新\(dp\)......
  • 题解:P1007 独木桥
    独木桥-洛谷https://www.luogu.com.cn/problem/P1007思路:输入部分:首先读取独木桥的长度 L 和初始留在桥上的士兵数目 N。然后通过循环读取每个士兵的初始坐标并存储在 soldiers 数组中。计算最小时间和最大时间:对于每个士兵,通过 min(soldiers[i],L+1-soldie......
  • 递归疑难问题解答
    1.计算一个数的每位之和(递归实现)写一个递归函数DigitSum(n),输入一个非负整数,返回组成它的数字之和例如,调用DigitSum(1729),则应该返回1+7+2+9,它的和是19输入:1729,输出:19#include<stdio.h>intfac(intn){ if(n<10) { returnn; } else { returnfac(n/10)+......
  • 题解:P3891 [GDOI2014] 采集资源
    P3891[GDOI2014]采集资源题意简述:开始时你有数量为\(m\)的资源,有\(n\)种“苦工”可以不限次数地建造,每种苦工都有一个花费\(a\),和一个效率\(b\),要求最小化资源数量到达\(t\)的时间Solution:我们考虑先对于每一种花费\(i\)最大化它的“单位时间内产生的资源的数量......
  • MQ消息乱序问题解析与实战解决方案
    1.背景在分布式系统中,消息队列(MQ)是实现系统解耦、异步通信的重要工具。然而,MQ消费时出现的消息乱序问题,经常会对业务逻辑的正确执行和系统稳定性产生不良影响。本文将详细探讨MQ消息乱序问题的根源,并提供一系列在实际应用中可行的解决方案。2.MQ消息乱序问题分析常见的MQ消息......
  • P7206 [COCI2019-2020#3] Lampice 题解
    显然可以对答案奇偶分别二分,判断用点分治。考虑对每个点记录到当前分治中心的路径正着和倒着的hash值,那么两个点之间的路径是回文路径可以用一个简单的式子表示,移项一下把跟一个点有关的值放到一边,用unordered_map记录/查询即可,需要卡常,时间复杂度\(\mathcalO(n\log^2n)\)。......