《算法藝術與信息學競賽》P－116：
提交方式：POJ1191
好久沒有寫文章了，隨便放一個題目在這里湊數(shù)：
題目描述：
棋盤分割
| Time Limit: 1000MS |
|
Memory Limit: 10000K |
| Total Submissions: 1302 |
|
Accepted: 463 |
Description
將一個８*８的棋盤進行如下分割：將原棋盤割下一塊矩形棋盤并使剩下部分也是矩形，再將剩下的部分繼續(xù)如此分割，這樣割了(n-1)次后，連同最后剩下的矩形棋盤共有n塊矩形棋盤。(每次切割都只能沿著棋盤格子的邊進行)
原棋盤上每一格有一個分值，一塊矩形棋盤的總分為其所含各格分值之和。現(xiàn)在需要把棋盤按上述規(guī)則分割成n塊矩形棋盤，并使各矩形棋盤總分的均方差最小。
均方差
，其中平均值
，x
i為第i塊矩形棋盤的總分。
請編程對給出的棋盤及n，求出O'的最小值。
Input
第1行為一個整數(shù)n(1 < n < 15)。
第2行至第9行每行為8個小于100的非負整數(shù)，表示棋盤上相應格子的分值。每行相鄰兩數(shù)之間用一個空格分隔。
Output
僅一個數(shù)，為O'（四舍五入精確到小數(shù)點后三位）。
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
Source
Noi 99
解題思路：
參照《算法藝術與信息學競賽》：
代碼：
1 /*********************************************************************
2 Author: littlekid
3 Created Time: 2008-2-27 17:08:36
4 Problem Source: POJ1191
5 Description:
6 ********************************************************************/
7 # include <iostream>
8 # include <cmath>
9 using namespace std;
10
11 const int maxint = 2000000000;
12
13 # define N 8
14
15 double ans;
16 int map[ N+1 ][ N+1 ], n;
17 int sum[ N+1 ][ N+1 ];//[ N+1 ][ N+1 ];
18 int f[16][ N+1 ][ N+1 ][ N+1 ][ N+1 ];
19
20 void init()
21 {
22 for (int i = 1; i <= N; i ++)
23 {
24 for (int j = 1; j <= N; j++)
25 {
26 scanf("%d", &map[i][j]);
27 }
28 }
29 }
30
31 void output()
32 {
33 printf("%.3lf\n", ans);
34 }
35
36 inline int cal_sum(int x1, int y1, int x2, int y2)
37 {
38 int tmp = sum[x2][y2]+sum[x1-1][y1-1] - sum[x1-1][y2]-sum[x2][y1-1];
39 return tmp*tmp;
40 }
41
42
43 void dp()
44 {
45 //
46 memset(sum, 0, sizeof(sum));
47 int tmp;
48 sum[0][0] = 0;
49 for (int i = 1; i <= N; i ++)
50 {
51 for (int j = 1; j <= N; j ++)
52 {
53 sum[i][j] = sum[i][j-1]+sum[i-1][j] - sum[i-1][j-1] + map[i][j];
54 }
55 }
56 memset(f, 0, sizeof(f));
57 for(int x1 = 1; x1 <= N; x1 ++)
58 {
59 for (int y1 = 1; y1 <= N; y1 ++)
60 {
61 for (int x2 = x1; x2 <= N; x2 ++)
62 {
63 for (int y2 = y1; y2 <= N; y2 ++)
64 {
65 f[1][x1][y1][x2][y2] = cal_sum(x1, y1, x2, y2);
66 }
67 }
68 }
69 }
70 for (int k = 2; k <= n; k ++)
71 {
72
73 for (int x1 = 1; x1 <= N; x1 ++)
74 {
75 for (int y1 = 1; y1 <= N; y1 ++)
76 {
77 for (int x2 = x1; x2 <= N; x2 ++)
78 {
79 for (int y2 = y1; y2 <= N; y2 ++)
80 {
81
82 f[k][x1][y1][x2][y2] = maxint;
83 for (int x = x1; x < x2; x ++)
84 {
85 tmp = min( f[k-1][x1][y1][x][y2] + cal_sum(x+1, y1, x2, y2), //sum[x+1][y1][x2][y2],
86 f[k-1][x+1][y1][x2][y2] + cal_sum(x1, y1, x, y2)); //sum[x1][y1][x][y2] );
87 if (f[k][x1][y1][x2][y2] > tmp) f[k][x1][y1][x2][y2] = tmp;
88 }
89 for (int y = y1; y < y2; y ++)
90 {
91 tmp = min( f[k-1][x1][y1][x2][y] + cal_sum(x1, y+1, x2, y2), //sum[x1][y+1][x2][y2],
92 f[k-1][x1][y+1][x2][y2] + cal_sum(x1, y1, x2, y) ); //sum[x1][y1][x2][y] );
93 if (f[k][x1][y1][x2][y2] > tmp) f[k][x1][y1][x2][y2] = tmp;
94 }
95 }
96 }
97 }
98 }
99 }
100 // cout << f[n][1][1][N][N] << endl; ///
101 ans = sqrt( f[n][1][1][N][N]/(double)n - sum[N][N]*sum[N][N]/(double)(n*n));
102 }
103
104 int main()
105 {
106 while (scanf("%d", &n) != EOF)
107 {
108 init();
109 dp();
110 output();
111 }
112 return 0;
113 }
114
115
posted on 2008-02-27 20:04
R2 閱讀(1958)
評論(1) 編輯 收藏 引用 所屬分類:
Problem Solving