国产一区二区三精品久久久无广告,欧美激情精品久久久久久久九九九 ,中文字幕亚洲综合久久2

EOJ 1096 棋盤分割（動態規劃）

/*
2

EOJ 1096 棋盤分割
3

----題目描述：
6

將一個 8*8 的棋盤進行如下分割：
8

將原棋盤割下一塊矩形棋盤并使剩下部分也是矩形，再將剩下部分繼續如此分割，
9

這樣割了 n-1 次后，連同最后剩下的矩形棋盤共有 n 塊矩形棋盤。
10

每次切割都只能沿著棋盤格子的邊進行。
11

原棋盤上每一格有一個分值，一塊矩形棋盤的總分為其所含各格分值之和。
13

現需要把棋盤按上述規則分割成 n 塊矩形棋盤，并使各矩形棋盤總分的均方差最小。
14

均方差 O' = sqrt( sigma((x[i]-avgX) * (x[i]-avgX)) / n )；
16

平均值 avgX = sigma(x[i]) / n；
17

其中 x[i] 為第 i 塊矩形棋盤的分。
18

請編程對給出的棋盤及 n，求出 O' 的最小值。
21

----輸入：
23

第 1 行為一個整數n(1 <= n <= 15 )；
25

第 2 行至第 9 行每行為 8 個小于 100 的非負整數，表示棋盤上相應格子的分值。每行相鄰兩數之間用一個空格分隔。
26

----輸出：
29

僅一個數，為O'（四舍五入精確到小數點后三位）。
31

----樣例輸入：
33

3
35

1 1 1 1 1 1 1 3
36

1 1 1 1 1 1 1 1
37

1 1 1 1 1 1 1 1
38

1 1 1 1 1 1 1 1
39

1 1 1 1 1 1 1 1
40

1 1 1 1 1 1 1 1
41

1 1 1 1 1 1 1 0
42

1 1 1 1 1 1 0 3
43

----樣例輸出：
45

1.633
47

----分析：
50

對給定棋盤和 n，
52

可以確定 avgX，
53

而為了確定 O'，可以窮舉所有可能的切割方案，從而找到最小值，
54

具體實現為記憶化搜索，或者動態規劃，以減少冗余計算。
55

具體見代碼注釋。
57

*/
58

/*************************************************************
62

版本四
63

實現同版本三，
64

修改之處為，
65

部分數組由 double 改為 int 且去掉了一個數組 a[][] 。
66

具體見代碼。
68

*/
69

/*
70

#include <stdio.h>
71

#include <math.h>
72

#define L 9
74

#define N 16
75

#define INF 1e150
76

int n, s[ L ][ L ];
78

double avgX, f[ L ][ L ][ L ][ L ][ N ];
79

void init() {
81

int i, j, u, v, k;
82

for ( i = 0; i < L; ++i ) {
83

s[ 0 ][ i ] = s[ i ][ 0 ] = 0;
84

}
85

for ( i = 1; i < L; ++i ) {
86

for ( j = 1; j < L; ++j ) {
87

s[ i ][ j ] = s[ i-1 ][ j ] + s[ i ][ j-1 ] - s[ i-1 ][ j-1 ] + s[ i ][ j ];
88

}
89

}
90

for ( i = 0; i < L; ++i ) {
91

for ( j = 0; j < L; ++j ) {
92

for ( u = 0; u < L; ++u ) {
93

for ( v = 0; v < L; ++v ) {
94

for ( k = 0; k < N; ++k ) {
95

f[i][j][u][v][k] = INF * 3;
96

}
97

}
98

}
99

}
100

}
101

avgX = ((double)(s[ L-1 ][ L-1 ])) / n;
102

}
103

104

double solve( int i, int j, int u, int v, int m ) {
105

double tmp, tf;
106

int p;
107

108

if ( INF * 2 > f[i][j][u][v][m] ) {
109

return f[i][j][u][v][m];
110

}
111

112

if ( 0 == m ) {
113

tmp = s[u][v] - s[i-1][v] - s[u][j-1] + s[i-1][j-1] - avgX;
114

return ( f[i][j][u][v][m] = tmp * tmp );
115

}
116

tf = INF;
117

for ( p = j; p < v; ++p ) {
118

tmp = solve(i,j,u,p,0) + solve(i,p+1,u,v,m-1);
119

if ( tmp < tf ) {
120

tf = tmp;
121

}
122

tmp = solve(i,j,u,p,m-1) + solve(i,p+1,u,v,0);
123

if ( tmp < tf ) {
124

tf = tmp;
125

}
126

}
127

for ( p = i; p < u; ++p ) {
128

tmp = solve(i,j,p,v,0) + solve(p+1,j,u,v,m-1);
129

if ( tmp < tf ) {
130

tf = tmp;
131

}
132

tmp = solve(i,j,p,v,m-1) + solve(p+1,j,u,v,0);
133

if ( tmp < tf ) {
134

tf = tmp;
135

}
136

}
137

return ( f[i][j][u][v][m] = tf );
138

}
139

140

int main() {
141

int i, j;
142

double ans;
143

scanf( "%d", &n );
144

for ( i = 1; i < L; ++i ) {
145

for ( j = 1; j < L; ++j ) {
146

scanf( "%d", &s[i][j] );
147

}
148

}
149

init();
150

ans = sqrt( solve(1, 1, L-1, L-1, n-1) / n );
151

printf( "%0.3lf\n", ans );
152

return 0;
153

}
154

*/
155

156

157

/*************************************************************
158

版本三
159

思路同版本二，記憶化搜索，
160

修改之處為，
161

對于無解的情況也要記憶，而版本二中忽略了這一點。
162

163

具體見代碼。
164

*/
165

/*
166

#include <stdio.h>
167

#include <math.h>
168

169

#define L 9
170

#define N 16
171

#define INF 1e150
172

173

int n;
174

double avgX, a[ L ][ L ], s[ L ][ L ], f[ L ][ L ][ L ][ L ][ N ];
175

176

void init() {
177

int i, j, u, v, k;
178

for ( i = 0; i < L; ++i ) {
179

s[ 0 ][ i ] = s[ i ][ 0 ] = 0;
180

}
181

for ( i = 1; i < L; ++i ) {
182

for ( j = 1; j < L; ++j ) {
183

s[ i ][ j ] = s[ i-1 ][ j ] + s[ i ][ j-1 ] - s[ i-1 ][ j-1 ] + a[ i ][ j ];
184

}
185

}
186

for ( i = 0; i < L; ++i ) {
187

for ( j = 0; j < L; ++j ) {
188

for ( u = 0; u < L; ++u ) {
189

for ( v = 0; v < L; ++v ) {
190

for ( k = 0; k < N; ++k ) {
191

f[i][j][u][v][k] = INF * 3;
192

}
193

}
194

}
195

}
196

}
197

avgX = s[ L-1 ][ L-1 ] / n;
198

}
199

200

double solve( int i, int j, int u, int v, int m ) {
201

double tmp, tf;
202

int p;
203

204

if ( INF * 2 > f[i][j][u][v][m] ) {
205

return f[i][j][u][v][m];
206

}
207

208

if ( 0 == m ) {
209

tmp = s[u][v] - s[i-1][v] - s[u][j-1] + s[i-1][j-1] - avgX;
210

return ( f[i][j][u][v][m] = tmp * tmp );
211

}
212

tf = INF;
213

for ( p = j; p < v; ++p ) {
214

tmp = solve(i,j,u,p,0) + solve(i,p+1,u,v,m-1);
215

if ( tmp < tf ) {
216

tf = tmp;
217

}
218

tmp = solve(i,j,u,p,m-1) + solve(i,p+1,u,v,0);
219

if ( tmp < tf ) {
220

tf = tmp;
221

}
222

}
223

for ( p = i; p < u; ++p ) {
224

tmp = solve(i,j,p,v,0) + solve(p+1,j,u,v,m-1);
225

if ( tmp < tf ) {
226

tf = tmp;
227

}
228

tmp = solve(i,j,p,v,m-1) + solve(p+1,j,u,v,0);
229

if ( tmp < tf ) {
230

tf = tmp;
231

}
232

}
233

return ( f[i][j][u][v][m] = tf );
234

}
235

236

int main() {
237

int i, j;
238

double ans;
239

scanf( "%d", &n );
240

for ( i = 1; i < L; ++i ) {
241

for ( j = 1; j < L; ++j ) {
242

scanf( "%lf", &a[i][j] );
243

}
244

}
245

init();
246

ans = sqrt( solve(1, 1, L-1, L-1, n-1) / n );
247

printf( "%0.3lf\n", ans );
248

return 0;
249

}
250

*/
251

252

253

/*************************************************************
254

版本二（TLE）
255

記憶化搜索。
256

257

函數 double solve( int i, int j, int u, int v, int m )
258

求解棋盤某局部切割 m 次所得到的最小 sigma((x[?]-avgX) * (x[?]-avgX))，
259

其中 x[?] 為從此局部中切割出的某塊矩形棋盤的分。
260

261

計算過程實現為窮舉本局部所有可行的切割方案，在窮舉中遞歸計算子問題。
262

263

計算后使用數組記錄本次計算的結果，
264

若再次計算相同的問題，則直接從數組中讀出，而不必重新計算。
265

266

具體見代碼。
267

*/
268

/*
269

#include <stdio.h>
270

#include <math.h>
271

272

#define L 9
273

#define N 16
274

#define INF 1e150
275

276

int n;
277

double avgX, a[ L ][ L ], s[ L ][ L ], f[ L ][ L ][ L ][ L ][ N ];
278

279

void init() {
280

int i, j, u, v, k;
281

for ( i = 0; i < L; ++i ) {
282

s[ 0 ][ i ] = s[ i ][ 0 ] = 0;
283

}
284

for ( i = 1; i < L; ++i ) {
285

for ( j = 1; j < L; ++j ) {
286

s[ i ][ j ] = s[ i-1 ][ j ] + s[ i ][ j-1 ] - s[ i-1 ][ j-1 ] + a[ i ][ j ];
287

}
288

}
289

for ( i = 0; i < L; ++i ) {
290

for ( j = 0; j < L; ++j ) {
291

for ( u = 0; u < L; ++u ) {
292

for ( v = 0; v < L; ++v ) {
293

for ( k = 0; k < N; ++k ) {
294

f[i][j][u][v][k] = INF + INF;
295

}
296

}
297

}
298

}
299

}
300

avgX = s[ L-1 ][ L-1 ] / n;
301

}
302

303

double solve( int i, int j, int u, int v, int m ) {
304

double tmp, tf;
305

int p;
306

307

if ( INF > f[i][j][u][v][m] ) {
308

return f[i][j][u][v][m];
309

}
310

311

if ( 0 == m ) {
312

tmp = s[u][v] - s[i-1][v] - s[u][j-1] + s[i-1][j-1] - avgX;
313

return ( f[i][j][u][v][m] = tmp * tmp );
314

}
315

tf = INF + INF;
316

for ( p = j; p < v; ++p ) {
317

tmp = solve(i,j,u,p,0) + solve(i,p+1,u,v,m-1);
318

if ( tmp < tf ) {
319

tf = tmp;
320

}
321

tmp = solve(i,j,u,p,m-1) + solve(i,p+1,u,v,0);
322

if ( tmp < tf ) {
323

tf = tmp;
324

}
325

}
326

for ( p = i; p < u; ++p ) {
327

tmp = solve(i,j,p,v,0) + solve(p+1,j,u,v,m-1);
328

if ( tmp < tf ) {
329

tf = tmp;
330

}
331

tmp = solve(i,j,p,v,m-1) + solve(p+1,j,u,v,0);
332

if ( tmp < tf ) {
333

tf = tmp;
334

}
335

}
336

return ( f[i][j][u][v][m] = tf );
337

}
338

339

int main() {
340

int i, j;
341

double ans;
342

scanf( "%d", &n );
343

for ( i = 1; i < L; ++i ) {
344

for ( j = 1; j < L; ++j ) {
345

scanf( "%lf", &a[i][j] );
346

}
347

}
348

init();
349

ans = sqrt( solve(1, 1, L-1, L-1, n-1) / n );
350

printf( "%0.3lf\n", ans );
351

return 0;
352

}
353

*/
354

355

356

/*************************************************************
357

版本一
358

動態規劃。
359

360

公式變形為 O' * O' = sigma(x[i]*x[i]) / n - avgX * avgX；
361

362

對棋盤某局部，左上角為(x1,y1)，右下角為(x2,y2)，
363

令
364

s[x1][y1][x2][y2] 為此局部的總分的平方，
365

d[k][x1][y1][x2][y2] 為此局部切割 k 次所得的最小的 sigma(x[?]*x[?])，
366

其中 x[?] 為從此局部中切割出的某塊矩形棋盤的分。
367

368

則
369

d[k][x1][y1][x2][y2] = min(
370

min(
371

d[k-1][x1][y1][c][y2] + s[c+1][y1][x2][y2],
372

s[x1][y1][c][y2] + d[k-1][c+1][y1][x2][y2]
373

) 其中 x1 <= c < x2；
374

375

min(
376

d[k-1][x1][y1][x2][c] + s[x1][c+1][x2][y2],
377

s[x1][y1][x2][c] + d[k-1][x1][c+1][x2][y2]
378

) 其中 y1 <= c < y2；
379

)
380

381

具體見代碼。
382

*/
383

/*
384

#include <stdio.h>
385

#include <string.h>
386

#include <math.h>
387

388

#define L 9
389

#define N 16
390

#define OO 2123456789
391

392

int n, sum[L][L], s[L][L][L][L];
393

double d[N][L][L][L][L];
394

395

int main(){
396

int x1, y1, x2, y2, k, c, x;
397

double tem, tt;
398

memset( sum, 0, sizeof(sum) );
399

400

scanf( "%d", &n );
401

for( x1=1; x1<L; ++x1 ){
402

for( y1=1; y1<L; ++y1 ){
403

scanf( "%d", &x );
404

sum[x1][y1] = sum[x1-1][y1] + sum[x1][y1-1] - sum[x1-1][y1-1] + x;
405

}
406

}
407

408

for( x1=1; x1<L; ++x1 ){
409

for( y1=1; y1<L; ++y1 ){
410

for( x2=x1; x2<L; ++x2 ){
411

for( y2=y1; y2<L; ++y2 ){
412

for( k=0; k<n; ++k ){
413

d[k][x1][y1][x2][y2] = OO;
414

}
415

416

x = sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1];
417

d[0][x1][y1][x2][y2] = s[x1][y1][x2][y2] = x * x;
418

}
419

}
420

}
421

}
422

423

for( k=1; k<n; ++k ){
424

for( x1=1; x1<L; ++x1 ){
425

for( y1=1; y1<L; ++y1 ){
426

for( x2=x1; x2<L; ++x2 ){
427

for( y2=y1; y2<L; ++y2 ){
428

tem = OO;
429

430

for( c=x1; c<x2; ++c ){
431

tt = d[k-1][x1][y1][c][y2] + s[c+1][y1][x2][y2];
432

if( tt < tem ){
433

tem = tt;
434

}
435

tt = s[x1][y1][c][y2] + d[k-1][c+1][y1][x2][y2];
436

if( tt < tem ){
437

tem = tt;
438

}
439

}
440

441

for( c=y1; c<y2; ++c ){
442

tt = d[k-1][x1][y1][x2][c] + s[x1][c+1][x2][y2];
443

if( tt < tem ){
444

tem = tt;
445

}
446

tt = s[x1][y1][x2][c] + d[k-1][x1][c+1][x2][y2];
447

if( tt < tem ){
448

tem = tt;
449

}
450

}
451

452

d[k][x1][y1][x2][y2] = tem;
453

}
454

}
455

}
456

}
457

}
458

459

printf( "%0.3lf\n", sqrt( d[n-1][1][1][8][8] / n - ( sum[8][8] * 1.0 / n ) * ( sum[8][8] * 1.0 / n ) ) );
460

return 0;
461

}
462

*/
463

posted on 2012-03-17 11:28 coreBugZJ 閱讀(748) 評論(0) 編輯收藏引用所屬分類: ACM 、Algorithm 、課內作業

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 微軟2014實習生及秋令營技術類職位在線測試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數碼問題，POJ 1077 Eight POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim POJ 3696 The Luckiest number POJ 3604 Professor Ben EOJ 1117 剩余定理

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術

開源

科學

數學

圖形圖像

文化

問題（練習＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

EOJ 1096 棋盤分割（動態規劃）

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術

開源

科學

數學

圖形圖像

文化

問題（練習＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

EOJ 1096 棋盤分割 （動態規劃）

EOJ 1096 棋盤分割（動態規劃）