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

            強(qiáng)烈推薦此題!
            一種巧妙的DP,稱為插頭DP。每個格子是一個階段,狀態(tài)是通過這個格子的右邊一個格子的左邊和上邊的S形折線(共由m+1條線段組成)上的3進(jìn)制數(shù)。

            這是題目的第一個sample,我把行、列都從1開始編號,原始圖設(shè)為g,紅線表示狀態(tài)f[2][2][(100221)3]。
            狀態(tài)設(shè)計好了,狀態(tài)轉(zhuǎn)移也就不是難事了。根據(jù)g[i][j + 1]的值來確定狀態(tài)轉(zhuǎn)移的方式。
            我是用順推的轉(zhuǎn)移,不大好表述,不懂的話看看代碼,再看看圖,想想就能明白。

            /*************************************************************************
            Author: WHU_GCC
            Created Time: 2007-9-24 19:35:22
            File Name: pku3133.cpp
            Description: 
            ***********************************************************************
            */

            #include 
            <iostream>
            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; }

            const int maxn = 10;
            const int mask[11= {1392781243729218765611968359049};

            int g[maxn][maxn];
            char f[maxn + 1][maxn][59049];
            int n, m;
            int pow3m;

            inline 
            int get_bit(int x, int k)
            {
                
            return x % mask[k + 1/ mask[k];
            }


            inline 
            int set_bit(int x, int k)
            {
                
            return x - get_bit(x, k) * mask[k] - get_bit(x, k + 1* mask[k + 1];
            }


            int dp()
            {
                pow3m 
            = mask[m + 1];
                memset(f, 
            0x7Fsizeof(f));
                f[
            1][0][0= 0;
                
            for (int i = 1; i <= n; i++)
                
            {
                    
            for (int j = 0; j < m; j++)
                        
            for (int k = 0; k < pow3m; k++if (f[i][j][k] != 0x7F)
                        
            {
                            
            int bit_j = get_bit(k, j);
                            
            int bit_j1 = get_bit(k , j + 1);
                            
            int pre_bit = set_bit(k, j);
                            
            if (g[i][j + 1== 1)
                            
            {
                                
            if (bit_j == 0 && bit_j1 == 0)
                                    f[i][j 
            + 1][k] <?= f[i][j][k];
                            }

                            
            else if (g[i][j + 1== 2)
                            
            {
                                
            if (bit_j + bit_j1 == 1)
                                    f[i][j 
            + 1][pre_bit] <?= f[i][j][k] + 1;
                                
            if (bit_j + bit_j1 == 0)
                                
            {
                                    f[i][j 
            + 1][pre_bit + mask[j]] <?= f[i][j][k] + 1;
                                    f[i][j 
            + 1][pre_bit + mask[j + 1]] <?= f[i][j][k] + 1;
                                }

                            }

                            
            else if (g[i][j + 1== 3)
                            
            {
                                
            if (bit_j == 0 && bit_j1 == 2 || bit_j == 2 && bit_j1 == 0)
                                    f[i][j 
            + 1][pre_bit] <?= f[i][j][k] + 1;
                                
            if (bit_j + bit_j1 == 0)
                                
            {
                                    f[i][j 
            + 1][pre_bit + 2 * mask[j]] <?= f[i][j][k] + 1;
                                    f[i][j 
            + 1][pre_bit + 2 * mask[j + 1]] <?= f[i][j][k] + 1;
                                }

                            }

                            
            else
                            
            {
                                
            if (bit_j == 1 && bit_j1 == 0 || bit_j == 0 && bit_j1 == 1)
                                
            {
                                    f[i][j 
            + 1][pre_bit + mask[j]] <?= f[i][j][k] + 1;
                                    f[i][j 
            + 1][pre_bit + mask[j + 1]] <?= f[i][j][k] + 1;
                                }

                                
            if (bit_j == 0 && bit_j1 == 2 || bit_j == 2 && bit_j1 == 0)
                                
            {
                                    f[i][j 
            + 1][pre_bit + 2 * mask[j]] <?= f[i][j][k] + 1;
                                    f[i][j 
            + 1][pre_bit + 2 * mask[j + 1]] <?= f[i][j][k] + 1;
                                }

                                
            if (bit_j == 1 && bit_j1 == 1 || bit_j + bit_j1 == 4)
                                    f[i][j 
            + 1][pre_bit] <?= f[i][j][k] + 1;
                                
            if (bit_j + bit_j1 == 0)
                                
            {
                                    f[i][j 
            + 1][pre_bit] <?= f[i][j][k];
                                    f[i][j 
            + 1][pre_bit + mask[j] + mask[j + 1]] <?= f[i][j][k] + 1;
                                    f[i][j 
            + 1][pre_bit + 2 * mask[j] + 2 * mask[j + 1]] <?= f[i][j][k] + 1;
                                }

                            }

                        }

                    
            for (int k = 0; k < pow3m / 3; k++)
                        f[i 
            + 1][0][k * 3= f[i][m][k];
                }

                
            if (f[n][m][0== 0x7F)
                    
            return 0;
                
            else
                    
            return f[n][m][0- 2;
            }


            int main()
            {
                
            while (scanf("%d%d"&n, &m), n + m != 0)
                
            {
                    
            for (int i = 1; i <= n; i++)
                        
            for (int j = 1; j <= m; j++)
                            scanf(
            "%d"&g[i][j]);
                    printf(
            "%d\n", dp());
                }

                
            return 0;
            }
            posted on 2007-09-24 21:12 Felicia 閱讀(1173) 評論(4)  編輯 收藏 引用 所屬分類: 動態(tài)規(guī)劃
            Comments
            • # re: [動態(tài)規(guī)劃]pku3133
              Run&Run
              Posted @ 2007-11-24 09:19
              0,1,2 分別表示什么狀態(tài)啊?  回復(fù)  更多評論   
            • # re: [動態(tài)規(guī)劃]pku3133
              Felicia
              Posted @ 2007-11-24 15:26
              看圖
              0表示沒有線穿過,1表示灰線穿過,2表示藍(lán)線穿過  回復(fù)  更多評論   
            • # re: [動態(tài)規(guī)劃]pku3133
              longshen
              Posted @ 2008-11-11 09:15
              看后對連通性狀態(tài)壓縮DP有點開竅了...

              謝謝!  回復(fù)  更多評論   
            • # re: [動態(tài)規(guī)劃]pku3133
              chuliuxiang
              Posted @ 2009-10-07 09:26
              還是有些不懂!  回復(fù)  更多評論   
             
            亚洲日韩中文无码久久| 久久毛片一区二区| 成人资源影音先锋久久资源网| 久久亚洲私人国产精品vA| 国产精品视频久久| 午夜精品久久久久成人| av色综合久久天堂av色综合在 | 99久久精品费精品国产一区二区| 97久久精品无码一区二区| 精品久久人人爽天天玩人人妻| 超级碰碰碰碰97久久久久| 99999久久久久久亚洲| 久久国产色av免费看| 久久成人国产精品一区二区| 久久精品中文字幕一区| 国产综合成人久久大片91| 日本久久久久亚洲中字幕| 伊人久久一区二区三区无码| 久久福利青草精品资源站免费| 国内精品综合久久久40p| 亚洲AⅤ优女AV综合久久久| 日本久久久久久中文字幕| 久久久久亚洲av无码专区喷水| 久久精品一区二区三区AV| 亚洲精品99久久久久中文字幕| 久久久久夜夜夜精品国产| 久久电影网一区| 人人狠狠综合久久亚洲88| 69久久精品无码一区二区| 人妻少妇久久中文字幕 | 久久精品夜色噜噜亚洲A∨| 国产精品99久久99久久久| 熟妇人妻久久中文字幕| 亚洲国产精品成人久久| 久久夜色精品国产网站| 久久99精品国产自在现线小黄鸭 | 久久精品国产精品亚洲精品 | 亚洲色婷婷综合久久| 伊人久久大香线蕉综合Av| 一本色道久久99一综合| 国内精品久久久久影院老司|