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

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>
            
国产精品日韩专区|
国产欧美日韩在线视频|
欧美va亚洲va国产综合|
欧美人成网站|
狠狠久久亚洲欧美|
亚洲精品久久7777|
性色av一区二区三区|
亚洲免费观看高清在线观看|
噜噜噜91成人网|
亚洲人成在线影院|
欧美电影在线观看完整版|
久久偷看各类wc女厕嘘嘘偷窃|
国产欧美91|
久久久亚洲综合|
久久精品国产精品亚洲综合|
国产亚洲欧美日韩日本|
香港久久久电影|
亚洲男女自偷自拍|
国产精品网站在线|
欧美一区激情|
欧美与欧洲交xxxx免费观看|
国产视频在线观看一区二区|
久久精品国产视频|
欧美在线免费一级片|
国模私拍一区二区三区|
鲁大师影院一区二区三区|
久久久精品tv|
亚洲国产欧美日韩精品|
亚洲国产欧美在线人成|
欧美freesex交免费视频|
亚洲美女在线观看|
一本久久综合亚洲鲁鲁五月天|
欧美婷婷六月丁香综合色|
亚洲欧美日韩精品久久久|
亚洲在线视频一区|
国产中文一区二区|
欧美国产日韩精品|
欧美视频免费在线|
久久久99久久精品女同性|
久久尤物视频|
中日韩在线视频|
亚洲综合三区|
91久久国产综合久久|
aa级大片欧美|
在线成人免费视频|
这里只有精品视频在线|
国产亚洲午夜|
亚洲精品麻豆|
激情婷婷欧美|
99国产一区二区三精品乱码|
国产一本一道久久香蕉|
亚洲精选视频在线|
精品动漫3d一区二区三区|
日韩一级片网址|
在线观看视频免费一区二区三区|
日韩视频免费大全中文字幕|
国产午夜精品视频免费不卡69堂|
亚洲国产成人久久综合一区|
国产精品伊人日日|
亚洲精品日韩欧美|
亚洲福利视频在线|
欧美一进一出视频|
亚洲尤物视频在线|
美女被久久久|
久久精品在线视频|
国产精品美女xx|
亚洲欧洲美洲综合色网|
一区二区三区精品在线|
亚洲午夜电影在线观看|
亚洲精品国产精品国自产在线|
亚洲自啪免费|
夜夜嗨av一区二区三区|
久久在线免费|
另类尿喷潮videofree|
国产伦精品一区|
在线一区免费观看|
亚洲无限乱码一二三四麻|
欧美激情亚洲另类|
亚洲国产精品一区制服丝袜
|
亚洲国产欧美久久|
欧美一区二区视频网站|
亚洲欧美国产不卡|
欧美午夜久久久|
一本色道久久综合精品竹菊|
99国产精品久久久久老师
|
一区二区三区视频在线看|
免费久久99精品国产|
欧美成人性网|
亚洲电影观看|
嫩模写真一区二区三区三州|
美腿丝袜亚洲色图|
亚洲高清在线播放|
久久婷婷综合激情|
麻豆av一区二区三区久久|
国产一区二区三区在线观看网站
|
国产精品国产三级国产aⅴ入口|
亚洲国产一区二区三区高清
|
久久精品国产99国产精品|
国产精品一区=区|
午夜精品一区二区在线观看|
欧美一区二区三区免费看|
国产无一区二区|
久久精品一区蜜桃臀影院|
欧美高清视频在线播放|
亚洲美女视频网|
欧美亚州在线观看|
香蕉久久国产|
欧美va天堂在线|
亚洲美女少妇无套啪啪呻吟|
欧美片在线播放|
亚洲私人影院|
久久夜色精品国产亚洲aⅴ|
欧美精品粉嫩高潮一区二区
|
欧美在线观看网站|
另类尿喷潮videofree|
亚洲黄色精品|
欧美天堂亚洲电影院在线播放
|
欧美激情综合亚洲一二区|
99精品欧美|
亚洲综合精品四区|
亚洲激情午夜|
国产精品久久毛片a|
久久精品视频网|
亚洲精选一区|
久久久夜色精品亚洲|
亚洲美女在线国产|
国产三级欧美三级|
韩日在线一区|
亚洲国产另类 国产精品国产免费|
欧美jizzhd精品欧美巨大免费|
亚洲精品在线免费观看视频|
午夜在线观看免费一区|
亚洲激情黄色|
国产女人精品视频|
欧美精品一区二区三区久久久竹菊|
亚洲一区免费|
亚洲福利视频一区|
欧美亚洲在线观看|
日韩西西人体444www|
国产一区二区三区在线观看视频|
欧美日本成人|
麻豆精品在线播放|
欧美一级精品大片|
一本一本a久久|
亚洲国产你懂的|
久久欧美中文字幕|
午夜精品久久久久久久99水蜜桃|
亚洲成人在线视频网站|
国产精品裸体一区二区三区|
欧美jjzz|
久久夜色精品国产欧美乱极品|
亚洲一区二区三区免费观看|
亚洲欧洲日韩在线|
欧美www视频在线观看|
性色av一区二区三区|
亚洲私人影院在线观看|
亚洲欧洲另类|
一区在线电影|
黄色av一区|
国产一区自拍视频|
国产精品一区二区你懂的|
欧美日韩精品系列|
欧美岛国在线观看|
免费在线欧美黄色|
麻豆freexxxx性91精品|
欧美在线亚洲综合一区|
亚洲综合视频在线|
亚洲一区二区三区影院|
日韩一级大片|
在线午夜精品|
中文日韩电影网站|
亚洲香蕉伊综合在人在线视看|
日韩视频二区|
亚洲视频在线一区|
亚洲五月六月|
亚洲天堂偷拍|
亚洲自啪免费|
欧美中日韩免费视频|
欧美亚洲免费电影|
欧美一二区视频|
久久国产欧美精品|
久久一区中文字幕|
久久久久久**毛片大全|
久久久午夜精品|
免费视频亚洲|
欧美日韩国产色综合一二三四
|
亚洲欧美99|
先锋影音久久久|
欧美在线综合视频|
久久久免费av|
欧美国产日本|
一本色道久久88综合亚洲精品ⅰ
|
久久久久国产一区二区三区|
久久午夜电影网|
欧美激情四色|
中国日韩欧美久久久久久久久|
午夜精品一区二区三区电影天堂
|
国产字幕视频一区二区|
经典三级久久|
欧美日韩在线播放三区四区|