• <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>
            隨筆 - 87  文章 - 279  trackbacks - 0
            <2006年9月>
            272829303112
            3456789
            10111213141516
            17181920212223
            24252627282930
            1234567

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊(cè)

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217919
            • 排名 - 117

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            棋盤分割
            Time Limit:1000MS? Memory Limit:10000K
            Total Submit:490 Accepted:194

            Description
            將一個(gè)8*8的棋盤進(jìn)行如下分割:將原棋盤割下一塊矩形棋盤并使剩下部分也是矩形,再將剩下的部分繼續(xù)如此分割,這樣割了(n-1)次后,連同最后剩下的矩形棋盤共有n塊矩形棋盤。(每次切割都只能沿著棋盤格子的邊進(jìn)行)


            原棋盤上每一格有一個(gè)分值,一塊矩形棋盤的總分為其所含各格分值之和。現(xiàn)在需要把棋盤按上述規(guī)則分割成n塊矩形棋盤,并使各矩形棋盤總分的均方差最小。
            均方差,其中平均值,xi為第i塊矩形棋盤的總分。
            請(qǐng)編程對(duì)給出的棋盤及n,求出O'的最小值。

            Input
            第1行為一個(gè)整數(shù)n(1 < n < 15)。
            第2行至第9行每行為8個(gè)小于100的非負(fù)整數(shù),表示棋盤上相應(yīng)格子的分值。每行相鄰兩數(shù)之間用一個(gè)空格分隔。

            Output
            僅一個(gè)數(shù),為O'(四舍五入精確到小數(shù)點(diǎn)后三位)。

            Sample Input

            3
            1 1 1 1 1 1 1 3
            1 1 1 1 1 1 1 1
            1 1 1 1 1 1 1 1
            1 1 1 1 1 1 1 1
            1 1 1 1 1 1 1 1
            1 1 1 1 1 1 1 1
            1 1 1 1 1 1 1 0
            1 1 1 1 1 1 0 3

            Sample Output

            1.633

            Source
            Noi 99

            #include? < iostream >
            #include?
            < cstdlib >
            #include?
            < cmath >
            using ? namespace ?std;

            const ? int ?INF? = ? 2000000000 ;
            int ?f[ 9 ][ 9 ][ 9 ][ 9 ][ 15 ];
            int ?s[ 9 ][ 9 ][ 9 ][ 9 ];
            int ?d[ 9 ][ 9 ];

            void ?init()
            {
            ????
            int ?x1,?y1,?x2,?y2;
            ????
            int ?i,?j;
            ????
            int ?sum;
            ????
            for ?(x1 = 1 ;?x1 <= 8 ;?x1 ++ )
            ????????
            for ?(y1 = 1 ;?y1 <= 8 ;?y1 ++ )
            ????????????
            for ?(x2 = x1;?x2 <= 8 ;?x2 ++ )
            ????????????????
            for ?(y2 = y1;?y2 <= 8 ;?y2 ++ )
            ????????????????
            {
            ????????????????????sum?
            = ? 0 ;
            ????????????????????
            for ?(i = x1;?i <= x2;?i ++ )
            ????????????????????????
            for ?(j = y1;?j <= y2;?j ++ )
            ????????????????????????????sum?
            += ?d[i][j];
            ????????????????????s[x1][y1][x2][y2]?
            = ?sum;
            ????????????????????f[x1][y1][x2][y2][
            1 ]? = ?sum? * ?sum;
            ????????????????}

            }

            int ?main()
            {

            ????
            int ?n;
            ????
            int ?i,?j,?k;
            ????
            int ?x1,?y1,?x2,?y2;
            ????
            int ?a,?b;
            ????
            int ?t,?tmp;
            ????
            double ?p? = ? 0 ;

            ????scanf(
            " %d " ,? & n);
            ????
            ????
            for ?(i = 1 ;?i <= 8 ;?i ++ )
            ????????
            for ?(j = 1 ;?j <= 8 ;?j ++ )
            ????????
            {
            ????????????scanf(
            " %d " ,? & d[i][j]);
            ????????????p?
            += ?d[i][j];
            ????????}


            ????p?
            /= ?n;
            // ????cout?<<?"???"<<?p?<<?endl;

            ????init();

            ????
            for ?(k = 2 ;?k <= n;?k ++ )
            ????
            {
            ????????
            for ?(x1 = 1 ;?x1 <= 8 ;?x1 ++ )
            ????????????
            for ?(y1 = 1 ;?y1 <= 8 ;?y1 ++ )
            ????????????????
            for ?(x2 = x1;?x2 <= 8 ;?x2 ++ )
            ????????????????????
            for ?(y2 = y1;?y2 <= 8 ;?y2 ++ )
            ????????????????????
            {
            ????????????????????????tmp?
            = ?INF;
            ????????????????????????
            // 豎切
            ???????????????????????? for ?(a = x1;?a < x2;?a ++ )
            ????????????????????????
            {
            ????????????????????????????t?
            = ?min(f[x1][y1][a][y2][k - 1 ] + s[a + 1 ][y1][x2][y2] * s[a + 1 ][y1][x2][y2]
            ????????????????????????????????,?f[a
            + 1 ][y1][x2][y2][k - 1 ] + s[x1][y1][a][y2] * s[x1][y1][a][y2]);
            ????????????????????????????
            if ?(tmp? > ?t)?
            ????????????????????????????????tmp?
            = ?t;
            ????????????????????????}

            ????????????????????????
            // 橫切
            ???????????????????????? for ?(b = y1;?b < y2;?b ++ )
            ????????????????????????
            {
            ????????????????????????????t?
            = ?min(f[x1][y1][x2][b][k - 1 ] + s[x1][b + 1 ][x2][y2] * s[x1][b + 1 ][x2][y2]
            ????????????????????????????????,?f[x1][b
            + 1 ][x2][y2][k - 1 ] + s[x1][y1][x2][b] * s[x1][y1][x2][b]);
            ????????????????????????????
            if ?(tmp? > ?t)
            ????????????????????????????????tmp?
            = ?t;
            ????????????????????????}

            ????????????????????????
            ????????????????????????f[x1][y1][x2][y2][k]?
            = ?tmp;
            ????????????????????}

            ????}

            ????printf(
            " %.3f\n " ,?sqrt( double (f[ 1 ][ 1 ][ 8 ][ 8 ][n]) / double (n) - p * p));
            ????
            return ? 0 ;
            }
            posted on 2006-09-08 22:57 閱讀(1318) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACM題目
            久久这里只精品99re66| 久久嫩草影院免费看夜色| 精品国产乱码久久久久久人妻| 国产毛片欧美毛片久久久| 亚洲国产精品高清久久久| 精品国产福利久久久| 久久强奷乱码老熟女网站| 久久精品天天中文字幕人妻 | 婷婷国产天堂久久综合五月| 亚洲国产香蕉人人爽成AV片久久| 无码人妻久久一区二区三区免费| segui久久国产精品| 亚洲人成精品久久久久| 精品乱码久久久久久夜夜嗨| 亚洲综合伊人久久综合| 国内精品久久久久久久亚洲 | 亚洲AⅤ优女AV综合久久久| 久久精品人成免费| 无码任你躁久久久久久久| 99久久这里只有精品| 亚洲午夜久久久久久久久久| 久久精品国产色蜜蜜麻豆| 97久久超碰国产精品2021| 一本色综合网久久| 欧美激情一区二区久久久| 久久91精品综合国产首页| 久久中文字幕一区二区| 精品无码久久久久久午夜| 蜜臀av性久久久久蜜臀aⅴ| 久久久国产99久久国产一| 无码任你躁久久久久久| 精品无码久久久久久久动漫| 青青青青久久精品国产h| 久久免费美女视频| 国产日产久久高清欧美一区| 国产欧美久久久精品| 久久青青草原综合伊人| 93精91精品国产综合久久香蕉 | 久久99国产精品99久久| 国产精品久久久亚洲| 国产精品美女久久久久|