『数学推导·平面DP』「NOI1999」棋盘分割

2023-10-13 12:59

本文主要是介绍『数学推导·平面DP』「NOI1999」棋盘分割,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

在这里插入图片描述

题解

这道题难就难在这一个均方差公式怎么搞,我们不妨对这一个算式进行化简。

在这里插入图片描述

= ∑ ( x i 2 − 2 ∗ x i ∗ x ‾ + n ∗ x ‾ 2 ) n =\sqrt \frac{\sum (x_i^2-2*x_i*\overline x+n*\overline x^2)}{n} =n(xi22xix+nx2)
= ∑ x i 2 − 2 ∗ ∑ x i ∗ x ‾ + n ∗ x ‾ 2 n =\sqrt \frac{\sum x_i^2-2*\sum x_i*\overline x+n*\overline x^2}{n} =nxi22xix+nx2
= ∑ x i 2 − 2 ∗ n ∗ x ‾ ∗ x ‾ + n ∗ x ‾ ∗ x ‾ n =\sqrt \frac{\sum x_i^2-2*n*\overline x*\overline x+n*\overline x*\overline x}{n} =nxi22nxx+nxx
= ∑ x i 2 − n ∗ x ‾ ∗ x ‾ n =\sqrt \frac{\sum x_i^2-n*\overline x*\overline x}{n} =nxi2nxx
= ∑ x i 2 n − x ‾ 2 =\sqrt{\frac{\sum x_i^2}{n}-\overline x^2} =nxi2x2

推到这里就很简洁明了啦!我们只要求解 ∑ x i \sum x_i xi的最小值即可。也就是每一个区域的平方和最小,这个用平面DP的方法可以很简单的得到,这里就不说了。

代码如下:

#include <iostream>
#include <cstdio>
#include <cmath>using namespace std;
const int N = 10;int n = 8, m;
int a[N][N], f[N][N][N][N][20];int s(int A,int b,int c,int d)
{int sum = a[c][d] - a[A-1][d] - a[c][b-1] + a[A-1][b-1];return sum * sum;
}int main(void)
{freopen("input.in","r",stdin);freopen("output.out","w",stdout);cin >> m;for (int i=1;i<=n;++i)for (int j=1;j<=n;++j)cin>>a[i][j], a[i][j] = a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j];for (int r=1;r<=m;++r)for (int i=1;i<=n;++i)for (int j=1;j<=n;++j)for (int k=i;k<=n;++k)for (int t=j;t<=n;++t){if (r == 1) { f[i][j][k][t][r] = s(i,j,k,t); continue; };f[i][j][k][t][r] = 1e9;for (int p=i;p<k;++p) f[i][j][k][t][r] = min(f[i][j][k][t][r],f[i][j][p][t][r-1]+s(p+1,j,k,t));for (int p=i;p<k;++p) f[i][j][k][t][r] = min(f[i][j][k][t][r],f[p+1][j][k][t][r-1]+s(i,j,p,t));for (int p=j;p<t;++p) f[i][j][k][t][r] = min(f[i][j][k][t][r],f[i][j][k][p][r-1]+s(i,p+1,k,t));for (int p=j;p<t;++p) f[i][j][k][t][r] = min(f[i][j][k][t][r],f[i][p+1][k][t][r-1]+s(i,j,k,p));	}int ans = f[1][1][8][8][m];int sum = s(1,1,8,8);printf("%.3lf",sqrt(ans*1.0/(m*1.0)-sum*1.0/(m*m*1.0)));return 0;
}

这篇关于『数学推导·平面DP』「NOI1999」棋盘分割的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/203386

相关文章

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

使用Python实现批量分割PDF文件

《使用Python实现批量分割PDF文件》这篇文章主要为大家详细介绍了如何使用Python进行批量分割PDF文件功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、架构设计二、代码实现三、批量分割PDF文件四、总结本文将介绍如何使用python进js行批量分割PDF文件的方法

使用C#代码计算数学表达式实例

《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来... 目录C#代码计算数学表达式该方法很长,因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如

使用Python将长图片分割为若干张小图片

《使用Python将长图片分割为若干张小图片》这篇文章主要为大家详细介绍了如何使用Python将长图片分割为若干张小图片,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. python需求的任务2. Python代码的实现3. 代码修改的位置4. 运行结果1. Python需求

C#中字符串分割的多种方式

《C#中字符串分割的多种方式》在C#编程语言中,字符串处理是日常开发中不可或缺的一部分,字符串分割是处理文本数据时常用的操作,它允许我们将一个长字符串分解成多个子字符串,本文给大家介绍了C#中字符串分... 目录1. 使用 string.Split2. 使用正则表达式 (Regex.Split)3. 使用

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

uva 10014 Simple calculations(数学推导)

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导,第二次没有继续下去。 代码: #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf