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

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)  編輯 收藏 引用 所屬分類: ACM 、Algorithm 、課內作業

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

    • <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国产精品|