• <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>
            不錯的DP題。狀態f[i][x1][y1][x2][y2]表示要把(x1,y1) -- (x2, y2) 分割成i塊所得到的最小平方和(平方和指的是每塊矩形的和的平方和)。然后根據水平和豎直切割進行狀態轉移。這樣計算出f[n][1][1][8][8]得到整個棋盤分割成n塊得到的最小平方和,然后代入均方差公式算得結果。


            /*************************************************************************
            Author: WHU_GCC
            Created Time: 2007-10-1 19:01:11
            File Name: pku1191.cpp
            Description: 
            ***********************************************************************
            */

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

            #define out(x) (cout << #x << ": " << x << endl)
            typedef 
            long long int64;
            const int maxint = 0x7FFFFFFF;
            const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
            template 
            <class T> void show(T a, int n) for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
            template 
            <class T> void show(T a, int r, int l) for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }

            int n;
            int a[9][9], g[9][9];
            int f[16][9][9][9][9];

            inline 
            int sum(int x1, int y1, int x2, int y2)
            {
                
            return (g[x2][y2] - g[x1 - 1][y2] - g[x2][y1 - 1+ g[x1 - 1][y1 - 1])
                    
            * (g[x2][y2] - g[x1 - 1][y2] - g[x2][y1 - 1+ g[x1 - 1][y1 - 1]);
            }


            int dp(int k, int x1, int y1, int x2, int y2)
            {
                
            if (f[k][x1][y1][x2][y2] != maxint)
                    
            return f[k][x1][y1][x2][y2];
                
            if (k == 1)
                    
            return f[k][x1][y1][x2][y2] = sum(x1, y1, x2, y2);
                
            if (x1 == x2 && y1 == y2)
                    
            return f[k][x1][y1][x2][y2] = sum(x1, y1, x2, y2);
                
            int ret = maxint;
                
            for (int i = x1; i < x2; i++)
                
            {
                    ret 
            <?= dp(k - 1, x1, y1, i, y2) + sum(i + 1, y1, x2, y2);
                    ret 
            <?= sum(x1, y1, i, y2) + dp(k - 1, i + 1, y1, x2, y2);
                }

                
            for (int i = y1; i < y2; i++)
                
            {
                    ret 
            <?= dp(k - 1, x1, y1, x2, i) + sum(x1, i + 1, x2, y2);
                    ret 
            <?= sum(x1, y1, x2, i) + dp(k - 1, x1, i + 1, x2, y2);
                }

                
            return f[k][x1][y1][x2][y2] = ret;
            }


            int main()
            {
                scanf(
            "%d"&n);
                
            for (int i = 1; i <= 8; i++)
                    
            for (int j = 1; j <= 8; j++)
                        scanf(
            "%d"&a[i][j]);
                memset(g, 
            0sizeof(g));

                
            for (int i = 0; i <= 8; i++)
                    
            for (int j = 0; j <= 8; j++)
                        g[i][j] 
            = g[i - 1][j] + g[i][j - 1- g[i - 1][j - 1+ a[i][j];
                
                
            for (int k = 0; k <= 15; k++)
                    
            for (int x1 = 1; x1 <= 8; x1++)
                        
            for (int y1 = 1; y1 <= 8; y1++)
                            
            for (int x2 = 1; x2 <= 8; x2++)
                                
            for (int y2 = 1; y2 <= 8; y2++)
                                    f[k][x1][y1][x2][y2] 
            = maxint;
                
                
            double sum = 0.0;
                
            for (int i = 1; i <= 8; i++)
                    
            for (int j = 1; j <= 8; j++)
                        sum 
            += a[i][j];
                sum 
            /= n;
                sum 
            *= sum;

                printf(
            "%.3lf\n", sqrt(dp(n, 1188/ double(n) - sum));
                
            return 0;
            }
            posted on 2007-10-08 09:12 Felicia 閱讀(808) 評論(1)  編輯 收藏 引用 所屬分類: 動態規劃
            Comments
             
            国产V综合V亚洲欧美久久| 999久久久无码国产精品| 久久久久国产| 久久天天躁狠狠躁夜夜躁2014| 波多野结衣AV无码久久一区| 久久天天躁狠狠躁夜夜网站| 秋霞久久国产精品电影院| 色诱久久av| 久久婷婷综合中文字幕| 青春久久| 伊人色综合久久天天| 精品国产日韩久久亚洲| 久久久久夜夜夜精品国产| 精品国产乱码久久久久软件| 国产精品免费久久久久久久久| 久久性精品| 97精品国产97久久久久久免费| 欧美日韩久久中文字幕| 中文精品久久久久国产网址 | 亚洲国产精品久久电影欧美| 久久综合久久久| 久久久久久国产精品无码超碰| 久久久久这里只有精品| 久久综合欧美成人| 国产人久久人人人人爽| 囯产极品美女高潮无套久久久 | 亚洲国产精品久久久久网站| 久久夜色精品国产噜噜亚洲AV| 亚洲日韩欧美一区久久久久我| 国产福利电影一区二区三区,免费久久久久久久精 | 久久久久久久久久免免费精品| 99久久精品国内| 久久亚洲精品人成综合网| 老男人久久青草av高清| 欧美午夜A∨大片久久 | 日韩欧美亚洲综合久久影院Ds| 久久综合九色综合精品| 久久高清一级毛片| 国产精品久久久久久久人人看| 国产精品久久婷婷六月丁香| 精品综合久久久久久98|