• <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>
            

    
            

            




            







												


        


            


            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 閱讀(766) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



亚洲日韩中文无码久久|
热re99久久精品国99热|
国产精品免费久久|
欧美亚洲另类久久综合婷婷|
中文字幕久久精品无码|
91久久香蕉国产熟女线看|
日日狠狠久久偷偷色综合免费
|
久久99这里只有精品国产|
久久久久久国产精品免费无码|
狠狠干狠狠久久|
久久天天躁狠狠躁夜夜躁2O2O
|
色偷偷88欧美精品久久久|
www.久久精品|
国产婷婷成人久久Av免费高清
|
国产精品久久久久jk制服|
亚洲伊人久久综合中文成人网|
色综合久久精品中文字幕首页
|
狠狠人妻久久久久久综合蜜桃|
看久久久久久a级毛片|
久久伊人五月丁香狠狠色|
久久夜色撩人精品国产|
色综合久久久久|
伊人久久大香线蕉精品|
免费精品99久久国产综合精品|
久久亚洲AV成人出白浆无码国产|
成人综合久久精品色婷婷|
久久精品亚洲精品国产欧美|
91精品国产高清久久久久久91|
久久精品草草草|
久久最新精品国产|
草草久久久无码国产专区|
AA级片免费看视频久久|
亚洲综合精品香蕉久久网97
|
国产精品综合久久第一页|
成人a毛片久久免费播放|
国产精品无码久久综合网|
久久久久国产|
精品人妻伦九区久久AAA片69|
久久99久国产麻精品66|
久久精品蜜芽亚洲国产AV|
精品一区二区久久|