POJ 1191 棋盘分割 （记忆化搜索）

POJ 1191 棋盘分割 （记忆化搜索）

Description

Input

第1行为一个整数n(1 < n < 15)。 第2行至第9行每行为8个小于100的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

Output

仅一个数，为O’（四舍五入精确到小数点后三位）。

Sample Input

31 1 1 1 1 1 1 31 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 01 1 1 1 1 1 0 3

Sample Output

1.633

思路

首先对方差公式进行化简，化简之后为 σ2=∑ni=1x2in−x¯2

然后使用dfs搜索时进行切割， ​​dp[x][y][a][b][k]​​​ 代表进行 ​​n-k​​​ 次切割以后矩阵 ​​(x,y)-(a,b)​​ 分值和的平方。

因为平均数是定值，要使方差最小，只能让各块的和尽可能的小。

AC 代码

#include#include#include#include#include#includeusing namespace std;#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。