棋盘分割
Time Limit: 1000MS |
|
Memory Limit: 10000K |
Total Submissions: 4513 |
|
Accepted: 1591 |
Description
将一个8*8的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的部分继续如此分割,这样割了(n-1)次后,连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)
原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘,并使各矩形棋盘总分的均方差最小。
均方差
,其中平均值
,x
i为第i块矩形棋盘的总分。
请编程对给出的棋盘及n,求出O'的最小值。
Input
第1行为一个整数n(1 < n < 15)。
第2行至第9行每行为8个小于100的非负整数,表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。
Output
仅一个数,为O'(四舍五入精确到小数点后三位)。
Sample Input
3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3
Sample Output
1.633
解答:
每一次切割有以下四种方法:
分享到:
相关推荐
标题“POJ3253-POJ3253-Fence Repair【STL优先队列】”指的是一个在线编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。该题目要求参赛者使用C++编程语言解决特定的问题,并且在解决方案中...
【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...
【标题】"POJ1426-Find The Multiple【BFS+同余模】"是一道来源于北京大学在线编程平台POJ的算法题目,主要涉及到了广度优先搜索(BFS)与同余模运算的知识点。这道题目要求解决的是寻找一个整数的倍数问题,可能...
标题中的“POJ1129-Channel Allocation”是指一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这个题目涉及到“四色定理”,这是图论领域的一个经典问题。 四色定理是图论中的一个重要...
【标题】"POJ3020-Antenna Placement"是一个经典的计算机编程竞赛题目,源自北京大学的在线评测系统POJ(PKU Online Judge)。这个题目挑战了参赛者在算法设计和实现上的能力。 【描述】"解题报告+AC代码"意味着这...
《POJ 1000 - 2000 部分题目 官方分类》 编程竞赛,特别是在线判题系统(如POJ,即Problem Online Judge)中的题目,是提升编程技能和算法理解的重要途径。POJ 1000 - 2000 是一个涵盖广泛的题目区间,包含了大量的...
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
【标题】"POJ1837-Balance"是一个在线编程竞赛题目,源自著名的编程练习平台POJ(Programming Online Judge)。这个题目旨在测试参赛者的算法设计和实现能力,特别是处理平衡问题的技巧。 【描述】"解题报告+AC代码...
【标题】"POJ2299-Ultra-QuickSort"是北京大学在线判题系统POJ上的一道编程题目,其主要涉及的算法是快速排序(Ultra-QuickSort)。快速排序是一种高效的排序算法,由C.A.R. Hoare在1960年提出。它的基本思想是采用...
【标题】"POJ1258-Agri-Net【Prim】" 是一个编程竞赛题目,来源于北京大学的在线评测系统POJ(Problem Online Judge)。这个题目主要涉及到图论中的一个重要算法——普里姆(Prim)算法。 【描述】"北大POJ1258-...
【标题】"POJ1010-STAMPS"是一个编程题目,来源于北京大学的在线判题系统POJ(Problem Set of Peking University),这是一处训练程序员算法技能和编程能力的平台。该题目旨在考察参赛者对动态规划或贪心算法的理解...
标题“POJ3414-Pots”是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这个题目主要考察的是算法设计和实现能力,通常涉及计算机科学中的数据结构和算法知识。 解题报告是参赛者在...
【标题】"POJ2503-Babelfish"是一个来自北京大学在线判题系统(POJ,Problem Online Judge)的编程题目。该题目要求参赛者编写程序解决特定的算法问题,通过编程语言实现,然后提交代码以供系统自动评测。 【描述】...
《POJ2525-Text Formalization:深入解析TrieTree》 在计算机科学的世界里,算法和数据结构是解决问题的关键。今天我们要探讨的是一个名为"POJ2525-Text Formalization"的问题,它涉及到一种高效的数据结构——Trie...
例如,如果问题是关于分割圆饼,可能需要处理角度计算和分配的问题;如果是派对问题,可能涉及组合优化。 在实际编程过程中,解决这类问题时还需要注意时间复杂度和空间复杂度的控制,确保程序能在有限的时间内完成...
【标题】"POJ1003-Hangover"是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这类题目通常要求参赛者编写程序来解决特定的算法问题,以此锻炼和测试编程技能及算法理解能力。 【描述...
【标题】"POJ1201-Intervals" 是北京大学在线编程平台POJ上的一道题目,这道题目主要涉及计算机科学中的算法设计与分析,尤其是数据结构和时间复杂度优化方面的知识。 【描述】"北大POJ1201-Intervals 解题报告+AC...
【标题】"POJ1009 - 边缘检测" 在计算机图形学与图像处理领域,边缘检测是一项至关重要的技术。北京大学编程平台POJ上的第1009题,"Edge Detection"(边缘检测),旨在让学生通过编程实现对图像进行边缘检测。此题...
【标题】"POJ1007-DNA Sorting"是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这个题目要求参赛者编写程序,对DNA序列进行排序,具体而言,就是对一系列由ATCG四种碱基组成的DNA字符...
标题中的"POJ1002-487-3279【Hash+Qsort】"是指一个编程挑战题目,通常在在线编程平台上出现,比如北京大学的Peking Online Judge (POJ)。这个题目结合了哈希表(Hash)和快速排序(Qsort)两种算法来解决问题。哈希...