• <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 糯米 閱讀(678) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            漂亮人妻被黑人久久精品| 无码任你躁久久久久久| 久久99国产亚洲高清观看首页| 秋霞久久国产精品电影院| 亚洲国产成人久久一区久久| 久久精品国产亚洲AV麻豆网站 | 久久综合给合久久狠狠狠97色| 精品久久久久久无码专区 | 国产精品无码久久四虎| 97精品依人久久久大香线蕉97 | 久久久久久极精品久久久| 久久香综合精品久久伊人| 美女久久久久久| 精品午夜久久福利大片| 国内高清久久久久久| 94久久国产乱子伦精品免费 | 久久久亚洲精品蜜桃臀| 99久久中文字幕| 国产成人精品综合久久久久| 久久人妻少妇嫩草AV蜜桃| 国产欧美久久一区二区| 狠狠色狠狠色综合久久| 伊人久久大香线蕉综合5g| 久久久精品国产亚洲成人满18免费网站 | 久久综合给合久久狠狠狠97色69| 久久综合一区二区无码| 激情综合色综合久久综合| 久久综合中文字幕| 久久国产亚洲高清观看| 久久久久亚洲Av无码专| 久久精品国产亚洲AV高清热| 日产精品99久久久久久| 天天爽天天狠久久久综合麻豆| 久久精品人妻中文系列| 中文字幕精品无码久久久久久3D日动漫 | 97精品依人久久久大香线蕉97 | 久久久久av无码免费网| 精品国产日韩久久亚洲| 2019久久久高清456| 亚洲欧美日韩中文久久| 久久精品无码专区免费东京热 |