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

            ArcTan

            dfs
            隨筆 - 16, 文章 - 117, 評論 - 6, 引用 - 0
            數據加載中……

            SRM551 DIV2 (水題+枚舉+DP)

            950 PT:
            題意:
                   給三種顏色的蛋糕A、B、C,每種有a,b,c個,共n個。
                   要把n個蛋糕放成一圈,相鄰的兩個顏色不能相同。

            思路:
                  DP:記憶化搜索!

                  dp[n][s[0]][s[1]][d][l]表示:還需要放n個,第一種還有s[0]個,第二種還有s[1]個,當前放的是第d種,最后一個是l種的方案數。
                  f(n,s,d,l)求還有n個需要放,當前放的是第d種,最后一個放的是第l種。s是個數數組。

            #define mod 1000000007
            #define maxn 52

            using namespace std;

            long long dp[maxn][maxn][maxn][3][3];

            class ColorfulCupcakesDivTwo{
            public:
                
            long long f(int n,int s[],int d,int l){
                    
            if (n==0 && d!=l)
                        
            return 1;
                    
            if (n==0)
                        
            return 0;
                    
            if (dp[n][s[0]][s[1]][d][l]!=-1)
                        dp[n][s[
            0]][s[1]][d][l];
                    
            long long ans=0;
                    
            for (int i=0;i<3;i++)
                        
            if (i!=&& s[i])
                        {
                            s[i]
            --;
                            ans
            +=f(n-1,s,i,l);
                            ans 
            %=mod;
                            s[i]
            ++;
                        }
                    
            return dp[n][s[0]][s[1]][d][l]=ans;
                }
                
            int countArrangements(string cupcakes){
                    memset(dp,
            -1,sizeof(dp));
                    
            int s[3]={0,0,0};
                    
            int N=cupcakes.length();
                    
            for (int i=0;i<N;i++)
                        s[cupcakes[i]
            -'A']++;
                    
            long long ans=0;
                    
            for (int i=0;i<3;i++)
                        
            if (s[i])
                        {
                            s[i]
            --;
                            ans
            +=f(N-1,s,i,i);
                            ans 
            %=mod;
                            s[i]
            ++;
                        }
                    
            return ans;
                }

            };

            posted on 2012-08-10 10:38 wangs 閱讀(151) 評論(0)  編輯 收藏 引用

            无夜精品久久久久久| 久久国产精品一国产精品金尊| 久久婷婷五月综合97色直播| 久久综合色老色| 久久久久人妻一区二区三区vr| 久久久久亚洲AV无码网站| 国产欧美久久久精品| 久久国产精品视频| 亚洲色婷婷综合久久| 久久亚洲中文字幕精品一区四| 久久精品国产亚洲AV影院| 精品国产乱码久久久久久郑州公司 | 久久久久久精品免费看SSS| 久久久久久精品无码人妻| 国内精品久久久久| 久久久久亚洲精品日久生情| 91久久精品国产免费直播| 性高湖久久久久久久久| 要久久爱在线免费观看| 热久久国产欧美一区二区精品| 久久精品中文騷妇女内射| 亚洲国产一成久久精品国产成人综合| 久久亚洲私人国产精品vA| 久久人人爽人人爽人人AV东京热| 久久精品国产精品亚洲下载| 99久久国产热无码精品免费| 精品水蜜桃久久久久久久| 久久美女人爽女人爽| 99久久精品国产毛片| 久久一日本道色综合久久| 久久精品国产亚洲αv忘忧草| 久久久久99精品成人片三人毛片| 久久精品综合一区二区三区| 91性高湖久久久久| 2020最新久久久视精品爱 | 久久精品一区二区三区AV| 日本高清无卡码一区二区久久 | 国内精品久久久久影院薰衣草| 久久精品综合网| 久久无码AV一区二区三区| 久久夜色精品国产噜噜噜亚洲AV|