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

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 閱讀(774) 評論(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>
            
久久亚洲一区二区|
亚洲第一在线综合网站|
亚洲伦理在线观看|
亚洲欧洲另类国产综合|
蘑菇福利视频一区播放|
欧美91精品|
亚洲精品国产精品国自产观看浪潮
|
午夜天堂精品久久久久|
欧美日韩亚洲一区二区三区四区|
亚洲精品一区二区三区樱花|
久久人人爽人人爽|
亚洲第一网站|
国产午夜精品全部视频播放|
午夜视频在线观看一区二区三区|
欧美一区二区三区在线视频|
国产视频一区三区|
欧美视频在线一区二区三区|
亚洲欧美另类在线|
久久久夜精品|
欧美一区二区三区日韩|
亚洲天堂成人|
国产丝袜一区二区|
国产精品三级视频|
久久青青草综合|
久久av在线看|
日韩视频中文字幕|
久久久久久久97|
一本色道综合亚洲|
国产亚洲精久久久久久|
欧美激情1区|
亚洲欧美在线视频观看|
亚洲黄色在线观看|
国产免费观看久久|
毛片一区二区|
亚洲欧美怡红院|
亚洲在线视频免费观看|
欧美福利电影网|
亚欧成人精品|
亚洲精选在线|
精品成人国产|
国产精品草莓在线免费观看|
老司机精品福利视频|
亚洲一区二区影院|
欧美亚洲视频一区二区|
日韩小视频在线观看专区|
亚洲日本欧美在线|
美女视频黄免费的久久|
亚洲欧美日韩在线不卡|
亚洲美女精品一区|
亚洲性线免费观看视频成熟|
亚洲清纯自拍|
在线视频亚洲|
999在线观看精品免费不卡网站|
国产一区二区三区在线观看视频|
国产在线观看一区|
国产乱码精品一区二区三区五月婷
|
亚洲精品美女久久7777777|
亚洲精品美女久久久久|
中文日韩在线视频|
久久成人18免费网站|
亚洲一区亚洲二区|
日韩性生活视频|
午夜免费久久久久|
久久久免费精品视频|
欧美激情四色|
欧美激情91|
一本不卡影院|
亚洲精品社区|
亚洲欧美在线磁力|
久久亚洲一区二区|
欧美性猛交xxxx免费看久久久|
国产精品尤物|
亚洲日本va午夜在线影院|
亚洲一区欧美|
免费高清在线视频一区·|
日韩视频一区二区三区在线播放
|
国内外成人免费激情在线视频|
亚洲第一区在线观看|
亚洲性视频h|
母乳一区在线观看|
中文一区二区|
亚洲激情国产|
午夜日韩激情|
欧美日韩精品伦理作品在线免费观看|
久久这里有精品15一区二区三区|
欧美日韩国产美女|
精品av久久久久电影|
亚洲一区中文|
欧美激情视频给我|
欧美尤物巨大精品爽|
欧美肉体xxxx裸体137大胆|
激情久久久久|
性久久久久久久久|
亚洲精品中文字|
久久蜜桃精品|
国产欧美另类|
亚洲成色999久久网站|
香蕉久久夜色精品|
亚洲理论在线观看|
久久亚洲精品欧美|
国产欧美一区二区精品性色
|
久久精品水蜜桃av综合天堂|
久久男人资源视频|
亚洲视频在线视频|
欧美一区二区三区免费看|
欧美日韩高清在线一区|
亚洲国产精品久久久久秋霞不卡|
亚洲精品网址在线观看|
美女久久一区|
欧美呦呦网站|
国产午夜精品美女视频明星a级
|
国产精品久久久久久久久久久久久久|
欧美国产在线视频|
亚洲电影免费观看高清|
久久精品亚洲精品国产欧美kt∨|
亚洲视频欧洲视频|
欧美特黄a级高清免费大片a级|
亚洲裸体俱乐部裸体舞表演av|
麻豆freexxxx性91精品|
一本色道久久综合狠狠躁篇的优点|
亚洲欧美日韩爽爽影院|
国产精品二区在线|
在线视频免费在线观看一区二区|
亚洲国产一区二区三区a毛片|
夜夜嗨av一区二区三区免费区|
欧美国产激情|
99国内精品久久久久久久软件|
亚洲国产成人精品女人久久久
|
在线精品国精品国产尤物884a|
久久久精品999|
欧美一区二区三区四区视频|
国产欧美在线观看一区|
久久国产精品99国产|
亚洲欧美在线磁力|
国内精品久久久久久久影视蜜臀
|
国产精品久久久久久户外露出|
亚洲图片欧洲图片av|
亚洲精品之草原avav久久|
欧美日韩在线播放|
亚洲与欧洲av电影|
亚洲免费视频网站|
国产亚洲美州欧州综合国|
久久久久久亚洲精品杨幂换脸|
欧美自拍偷拍午夜视频|
在线观看日韩精品|
亚欧成人精品|
久久国产精品黑丝|
国产精品爱啪在线线免费观看|
亚洲一区二区在线|
亚洲免费中文|
黄色一区三区|
亚洲国产精品ⅴa在线观看|
欧美精品高清视频|
亚洲欧洲日韩综合二区|
亚洲激情视频在线播放|
欧美日韩中文字幕在线|
欧美伊人久久|
久久先锋影音|
日韩一级大片|
在线视频日韩精品|
国自产拍偷拍福利精品免费一|
欧美一区二区久久久|
久久成人亚洲|
伊人久久综合|
亚洲免费激情|
国产一区香蕉久久|
亚洲国产日韩一区二区|
国产精品成人av性教育|
久久久久国产精品午夜一区|
欧美r片在线|
欧美在线视频播放|
欧美岛国激情|
亚洲另类一区二区|
亚洲欧美卡通另类91av|
91久久久久久久久久久久久|
国产精品99久久久久久久久|
在线播放一区|
亚洲香蕉网站|
亚洲国产99|
亚洲欧美一区二区视频|
99xxxx成人网|
久久久久久**毛片大全|
在线看一区二区|
亚洲一区二区高清视频|
在线观看福利一区|
亚洲综合大片69999|
亚洲麻豆av|
久久久综合网|
性色av一区二区三区|
欧美精品一区二区三区在线看午夜
|
美女成人午夜|
欧美一区二区成人|
欧美精品入口|
男人插女人欧美|
国产女主播视频一区二区|
亚洲人www|
亚洲国产精品免费|
午夜欧美大尺度福利影院在线看|
亚洲伦理自拍|
免费成人你懂的|