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

            糯米

            TI DaVinci, gstreamer, ffmpeg
            隨筆 - 167, 文章 - 0, 評論 - 47, 引用 - 0
            數據加載中……

            POJ 1187 隕石的秘密 動態規劃

            #include <stdio.h>

            #define MOD(x) (((x) + 11380) % 11380)

            int L1, L2, L3, D, f[11][11][11][31];

            inline 
            int part(int ma, int mb, int mc, int md, 
                            
            int a, int b, int c
                            )
            {
                
            return MOD(f[a][b][c][md - 1* f[ma - a][mb - b][mc - c][md]);
            }


            inline 
            int calc(int ma, int mb, int mc, int md)
            {
                
            int a, b, c, r;

                
            if (!ma && !mb && !mc)
                    
            return 1;

                r 
            = 0;
                
            if (mc) {
                    
            for (c = 0; c <= mc - 1; c++)
                        r 
            = MOD(r + part(ma, mb, mc - 1, md, 00, c));
                }

                
            if (mb) {
                    
            for (b = 0; b <= mb - 1; b++)
                        
            for (c = 0; c <= mc; c++)
                            r 
            = MOD(r + part(ma, mb - 1, mc, md, 0, b, c));
                }

                
            if (ma) {
                    
            for (a = 0; a <= ma - 1; a++)
                        
            for (b = 0; b <= mb; b++)
                            
            for (c = 0; c <= mc; c++)
                                r 
            = MOD(r + part(ma - 1, mb, mc, md, a, b, c));
                }

                
            return r;
            }


            int main()
            {
                
            int a, b, c, d;

                freopen(
            "e:\\in.txt""r", stdin);

                scanf(
            "%d%d%d%d"&L1, &L2, &L3, &D);

                f[
            0][0][0][0= 1;
                
            for (d = 1; d <= D; d++
                    
            for (a = 0; a <= L1; a++)
                        
            for (b = 0; b <= L2; b++)
                            
            for (c = 0; c <= L3; c++)
                                f[a][b][c][d] 
            = calc(a, b, c, d);

                printf(
            "%d\n", D ? MOD(f[L1][L2][L3][D] - f[L1][L2][L3][D - 1]) : 
                                   MOD(f[L1][L2][L3][D])
                            );

                
            return 0;
            }

            思路:

            把括號的嵌套看成是一棵樹就簡單點了。
            這棵樹的最大深度為 D。()節點下面不能有{}[]節點,[]節點下面不能有{}節點。
            然后我們從上往下依次擺放節點。

            考慮只有()節點的情況。
            如果 f[n][d] 表示現在有n個節點需要擺放,深度小于等于d。
            那么當前節點的下面可以擺 1,2 ... n 個節點。
            擺完當前節點之后,剩下的在右邊繼續擺。
            總方案數就是等于 下面的方案數*右邊的方案數

            考慮三種節點都有的情況,實際上只是比上面的問題復雜一點點而已。
            如果 f[a][b][c][d] 表示現在有a個{}節點,b個[]節點,c個()節點需要擺放。
            當前節點擺 () 的時候,下面就只能擺 (),其余的全放在右邊。
            當前節點擺 [] 的時候,下面就只能擺 ()[],。。。
            。。。

            這題的復雜度是 O(L1*L1*L2*L2*L3*L3*D)。
            看上去比較大,但是可以AC的~

            之前自己想的方法是 f[a][b][c][d] 表示深度等于d的方案數,而不是小于。
            最后答案為 f[L1][L2][L3][D]。
            復雜度多乘了一個D,就TLE了。

            后來看了別人方法,發現保存深度小于等于d,這樣的話會好一些。
            最后答案為 f[L1][L2][L3][D] - f[L1][L2][L3][D - 1]
            這方法實在牛逼!

            代碼:


            posted on 2010-05-06 21:56 糯米 閱讀(668) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            99久久综合狠狠综合久久| 亚洲va久久久久| 人妻精品久久无码专区精东影业| 亚洲国产天堂久久久久久| 亚洲精品视频久久久| 免费久久人人爽人人爽av| 久久久久人妻精品一区二区三区 | 国产香蕉97碰碰久久人人| 国产精品成人久久久久久久| 久久受www免费人成_看片中文 | 亚洲精品无码久久久久久| 久久久久久久久无码精品亚洲日韩 | 久久超乳爆乳中文字幕| 午夜精品久久久内射近拍高清| 麻豆精品久久久久久久99蜜桃| 91精品国产综合久久香蕉| 波多野结衣久久一区二区| 国产一级持黄大片99久久| 亚洲国产成人久久综合碰| 狠狠色丁香婷综合久久| 国产精品乱码久久久久久软件| 青青草原综合久久| 中文字幕日本人妻久久久免费 | 热re99久久6国产精品免费| 精品国产青草久久久久福利| 精品久久久久中文字幕日本| 亚洲国产精品无码久久久久久曰 | 久久精品国产2020| 久久久久国产一区二区| 亚洲国产天堂久久综合网站| 亚洲国产精品无码久久98| 伊人久久大香线蕉AV一区二区| 国内精品久久久久久麻豆| 国产精品成人精品久久久| 青青国产成人久久91网| 国产精品久久久久久| 久久久久久九九99精品| 久久综合亚洲欧美成人| 亚洲AV无码1区2区久久| 久久天堂AV综合合色蜜桃网| 久久婷婷五月综合97色|