青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

此 blog 已棄。

EOJ 1096 棋盤分割 (動態規劃)

  1/*
  2EOJ 1096 棋盤分割
  3
  4
  5----題目描述:
  6
  7將一個 8*8 的棋盤進行如下分割:
  8將原棋盤割下一塊矩形棋盤并使剩下部分也是矩形,再將剩下部分繼續如此分割,
  9這樣割了 n-1 次后,連同最后剩下的矩形棋盤共有 n 塊矩形棋盤。
 10每次切割都只能沿著棋盤格子的邊進行。
 11
 12原棋盤上每一格有一個分值,一塊矩形棋盤的總分為其所含各格分值之和。
 13現需要把棋盤按上述規則分割成 n 塊矩形棋盤,并使各矩形棋盤總分的均方差最小。
 14
 15均方差 O'    = sqrt( sigma((x[i]-avgX) * (x[i]-avgX)) / n );
 16平均值 avgX  = sigma(x[i]) / n;
 17其中  x[i] 為第 i 塊矩形棋盤的分。
 18
 19
 20請編程對給出的棋盤及 n,求出 O' 的最小值。
 21
 22----輸入:
 23
 24第 1 行為一個整數n(1 <= n <= 15 );
 25第 2 行至第 9 行每行為 8 個小于 100 的非負整數,表示棋盤上相應格子的分值。每行相鄰兩數之間用一個空格分隔。
 26
 27
 28----輸出:
 29
 30僅一個數,為O'(四舍五入精確到小數點后三位)。
 31
 32----樣例輸入:
 33
 343
 351 1 1 1 1 1 1 3
 361 1 1 1 1 1 1 1
 371 1 1 1 1 1 1 1
 381 1 1 1 1 1 1 1
 391 1 1 1 1 1 1 1
 401 1 1 1 1 1 1 1
 411 1 1 1 1 1 1 0
 421 1 1 1 1 1 0 3
 43
 44----樣例輸出:
 45
 461.633
 47
 48
 49----分析:
 50
 51對給定棋盤和 n,
 52可以確定 avgX,
 53而為了確定 O',可以窮舉所有可能的切割方案,從而找到最小值,
 54具體實現為 記憶化搜索,或者動態規劃,以減少冗余計算。
 55
 56具體見代碼注釋。
 57*/

 58
 59
 60
 61/*************************************************************
 62版本四
 63實現同版本三,
 64修改之處為,
 65部分數組由 double 改為 int 且去掉了一個數組 a[][] 。
 66
 67具體見代碼。
 68*/

 69/*
 70#include <stdio.h>
 71#include <math.h>
 72
 73#define  L     9
 74#define  N     16
 75#define  INF   1e150
 76
 77int    n, s[ L ][ L ];
 78double avgX, f[ L ][ L ][ L ][ L ][ N ];
 79
 80void 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
104double 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
140int 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
173int n;
174double  avgX, a[ L ][ L ], s[ L ][ L ], f[ L ][ L ][ L ][ L ][ N ];
175
176void 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
200double 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
236int 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
276int n;
277double  avgX, a[ L ][ L ], s[ L ][ L ], f[ L ][ L ][ L ][ L ][ N ];
278
279void 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
303double 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
339int 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
364s[x1][y1][x2][y2]    為此局部的總分的平方,
365d[k][x1][y1][x2][y2] 為此局部切割 k 次所得的最小的 sigma(x[?]*x[?]),
366其中 x[?] 為從此局部中切割出的某塊矩形棋盤的分。
367
368
369d[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
392int    n, sum[L][L], s[L][L][L][L];
393double d[N][L][L][L][L];
394
395int 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 閱讀(773) 評論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithm課內作業

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欧美77777| 亚洲乱码国产乱码精品精 | 日韩亚洲欧美中文三级| 裸体歌舞表演一区二区| 噜噜噜在线观看免费视频日韩| 久久精品国产久精国产思思| 久久九九热re6这里有精品| 久久三级福利| 亚洲国产精品成人精品| 亚洲国产成人精品视频| 最近中文字幕日韩精品| a4yy欧美一区二区三区| 午夜免费久久久久| 麻豆国产精品777777在线 | 欧美国产高清| 国产精品国产三级国产专播品爱网 | aa级大片欧美三级| 亚洲女ⅴideoshd黑人| 欧美专区18| 欧美福利视频网站| 亚洲午夜久久久久久久久电影网| 欧美一级午夜免费电影| 欧美成人久久| 国产日韩精品一区| 日韩视频在线永久播放| 久久久久久久综合日本| 亚洲精品一区在线| 久久美女性网| 国产伦精品一区二区三区免费| 亚洲第一久久影院| 亚洲女人小视频在线观看| 噜噜噜91成人网| 中文国产一区| 欧美激情精品久久久久久久变态| 国产视频亚洲精品| 一本综合精品| 欧美激情第9页| 久久电影一区| 国产精品免费网站在线观看| 日韩视频免费观看高清完整版| 欧美在线黄色| 亚洲视频 欧洲视频| 欧美人与性动交α欧美精品济南到| 国内精品视频666| 午夜视频一区二区| 一本久久精品一区二区| 欧美大片va欧美在线播放| 在线成人免费视频| 久久免费的精品国产v∧| 亚洲一区二区三区四区视频| 欧美日本精品| 亚洲国产美女| 欧美多人爱爱视频网站| 久久男人资源视频| 狠狠色狠狠色综合| 开心色5月久久精品| 亚洲欧美综合精品久久成人| 国产精品激情| 午夜视频在线观看一区| 亚洲专区免费| 国产欧美欧美| 久久成人免费| 久久国产天堂福利天堂| 国产一区二区三区免费不卡| 久久成人一区| 久久免费国产精品| 亚洲国产一二三| 亚洲国产另类久久久精品极度| 免费观看30秒视频久久| 亚洲精品小视频| 亚洲老司机av| 国产精品色一区二区三区| 小辣椒精品导航| 一本久道久久综合狠狠爱| 久久www免费人成看片高清| 亚洲欧美日产图| 国产精品羞羞答答| 久久精品123| 久久综合影视| 亚洲视频在线观看三级| 亚洲午夜一级| 国产自产高清不卡| 欧美激情一区二区三区 | 国产精品美女黄网| 久久久www成人免费无遮挡大片| 欧美亚洲综合另类| 亚洲国产精品一区在线观看不卡 | 欧美电影免费观看大全| 一区二区三区视频观看| 亚洲欧美国产va在线影院| 在线观看一区欧美| 一卡二卡3卡四卡高清精品视频| 国产日韩一区二区三区在线播放| 久久综合久久综合久久综合| 欧美精品在线观看91| 亚洲一区二区精品视频| 欧美中文字幕在线播放| aⅴ色国产欧美| 欧美在线999| 一区二区欧美亚洲| 久久人人爽人人爽| 欧美亚洲色图校园春色| 欧美激情综合五月色丁香| 久久久久国产精品www| 欧美日韩成人激情| 女仆av观看一区| 国产精品亚洲人在线观看| 欧美激情在线狂野欧美精品| 国产欧美精品va在线观看| 亚洲精品日韩激情在线电影| 又紧又大又爽精品一区二区| 亚洲一区二区三区高清 | 久久久久久电影| 欧美三级在线视频| 欧美激情欧美狂野欧美精品| 国产亚洲美州欧州综合国| 日韩亚洲精品电影| 亚洲精品日韩在线观看| 久久久久久亚洲精品杨幂换脸 | 日韩午夜在线| 欧美在线观看一区二区| 亚洲欧美色一区| 欧美国产日韩一二三区| 美女国内精品自产拍在线播放| 国产美女高潮久久白浆| 免费日韩av电影| 久久综合影音| 精品不卡一区| 欧美亚洲一级片| 亚洲男人第一av网站| 欧美另类人妖| 亚洲免费高清视频| 一本久道久久综合中文字幕| 免费亚洲一区| 欧美激情久久久| 亚洲国产三级在线| 久久亚洲影院| 欧美成人tv| 在线视频国内自拍亚洲视频| 久久久免费精品| 欧美www在线| 91久久在线观看| 欧美精品v日韩精品v国产精品| 91久久精品日日躁夜夜躁欧美| 亚洲黄色小视频| 麻豆精品一区二区av白丝在线| 男女视频一区二区| 亚洲精品一区中文| 欧美日韩国产精品一卡| 亚洲伦理在线| 亚洲欧美日韩区| 国产亚洲精品aa| 久久影院午夜论| 亚洲国产成人精品视频| 一区二区免费在线播放| 国产精品日韩精品欧美在线| 先锋亚洲精品| 欧美黄色一区| 亚洲图片在线观看| 国产日韩欧美精品综合| 老司机免费视频一区二区三区| 欧美激情一区二区三区全黄| 99国产精品| 国产伦理精品不卡| 麻豆免费精品视频| 99热在线精品观看| 久久久精品一区| 一本久道综合久久精品| 国产日韩欧美三区| 欧美高清在线观看| 亚洲欧美视频一区| 亚洲第一在线综合在线| 午夜欧美不卡精品aaaaa| 在线视频观看日韩| 国产精品日本一区二区| 欧美777四色影视在线| 欧美一级免费视频| 亚洲精品一区二区三区樱花| 老司机一区二区三区| 在线一区二区三区四区五区| 国产一区二区三区久久精品| 欧美精品日韩精品| 久久国产高清| 99视频一区二区| 欧美国产先锋| 久久久国产精品一区| 亚洲影院一区| 亚洲精品视频二区| 极品日韩av| 国产伦精品一区二区三区四区免费| 欧美成年人网| 久久亚洲春色中文字幕久久久 | 久久久精品久久久久| 日韩午夜在线播放| 欧美激情精品久久久久| 久久久999精品免费| 麻豆成人在线| 香蕉国产精品偷在线观看不卡| 欧美激情在线免费观看| 两个人的视频www国产精品|