Shen Huang's Blog
0%

POJ 1191 棋盘分割

Posted on Edited on

主要是先把方差公式划简一下，然后进行分割，在哪一块割多少刀。

然后一开始出现用方格作为单位的时候出现不能计算x1==x2之类的情况，解决的办法就是做线段的分割，把坐标作为单位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/* POJ 1191 黑书p116 例题 主要是判断如何切 dp数组的维数开得很多
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define maxn 22
#define INF 1e8
int map[maxn][maxn];
int s[9][9][9][9],dp[16][9][9][9][9];
using namespace std;

int solve(int k,int x1,int y1,int x2,int y2){
	int Min = INF;
	for (int a = x1; a < x2; ++a)
		Min = min(Min,min(dp[k-1][x1][y1][a][y2]+s[a][y1][x2][y2],
					dp[k-1][a][y1][x2][y2]+s[x1][y1][a][y2]));
	for (int a = y1; a < y2; ++a)
		Min = min(Min,min(dp[k-1][x1][y1][x2][a]+s[x1][a][x2][y2],
					dp[k-1][x1][a][x2][y2]+s[x1][y1][x2][a]));
	return Min;

}

int main(){
	int n;
	while(~scanf("%d", &n)){
	memset(map,0,sizeof(map));
	for (int i = 1; i <= 8; ++i)
		for (int j = 1; j <= 8; ++j)
		{
			scanf("%d", &map[i][j]);
			map[i][j] += map[i-1][j] + map[i][j-1] -map[i-1][j-1];
			//cout<<map[i][j]<<endl;
		}
	for (int x1 = 0; x1 < 8; ++x1)
		for (int y1 = 0; y1 < 8; ++y1)
			for (int x2 = x1 + 1; x2 <= 8; ++x2)
				for (int y2 = y1 + 1; y2 <= 8; ++y2){
					s[x1][y1][x2][y2] = map[x2][y2] + 
					 map[x1][y1] - map[x1][y2] - map[x2][y1];
					dp[1][x1][y1][x2][y2] = s[x1][y1][x2][y2] * s[x1][y1][x2][y2];
					s[x1][y1][x2][y2] = dp[1][x1][y1][x2][y2];
				}
	for (int k = 2; k <=n; ++k)
	 for (int x1 = 0; x1 < 8; ++x1)
	  for (int y1 = 0; y1 < 8; ++y1)
	   for (int x2 = x1 + 1; x2 <= 8; ++x2)
	    for (int y2 = y1 + 1; y2 <= 8; ++y2){
			dp[k][x1][y1][x2][y2] = solve(k,x1,y1,x2,y2);
			//cout<<dp[k][x1][y1][x2][y2]<<endl;
		}
	double ans = 1.0 * dp[n][0][0][8][8] / n - 1.0 * map[8][8] * map[8][8] / n / n;
	printf("%.3fn", sqrt(ans));
	}
	return 0;
}