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

            Why so serious? --[NKU]schindlerlee

            2010年1月12日星期二.sgu223 狀態壓縮動態規劃

            2010年1月12日星期二.sgu223
             狀態壓縮動態規劃

            sgu223:n*n的棋盤上放置k個王的放置方法。
            基本方法和pku1185中的遞推方法是一樣的。
            都是先求出一行中的所有合法狀態,然后進行按行遞推,
            在遞推的過程中判斷兩行之間是否有沖突。

            #define L(n) (n << 1)
            #define R(n) (n >> 1)
            #define bin(n) (1 << n)
            #define low(n) (n & (-n))
            //http://www.shnenglu.com/schindlerlee/
            const int N = 10;
            int n,sum,full;
            int s[bin(N)],c[bin(N)],top;

            LL f[N
            +3][bin(N)][N*N];
            //行 最后一行狀態 已用的王的個數

            bool judgeRow(int t)
            {
              
            int stat = t,cnt = 0;
              
            int tp = 0,b = 0;
              
            while(t > 0) {
                  
            if(b & t) {
                      
            return false;
                  }
                  b 
            = t & 1,t >>= 1;
                  
            if(b == 1) cnt ++;
              }
              
            if(sum < cnt)
                
            return false;

              s[top] 
            = stat,c[top] = cnt,top++;
              
            return true;
            }

            bool contradict(int up,int down)
            return ((up & down) || (L(up) & down) || (R(up) & down)); }

            int main()
            {
              
            int i,j,k;
              scanf(
            "%d%d",&n,&sum);
              full 
            = bin(n) - 1;
              memset(f,
            0,sizeof(f));
              
            for(i = 0;i <= full;i++) {
                  judgeRow(i);
              }

              f[
            0][0][0= 1;
              
            for(i = 1;i <= n;i++) {
                  
            for(j = 0;j < top;j++) {
                      
            int s1 = s[j],c1 = c[j]; //current

                      
            for(k = 0;k < top;k++) {
                          
            for(int c2 = 0;c2 <= sum;c2++) {
                              
            int s2 = s[k];
                              
            if(!f[i-1][s2][c2] ||c1 + c2 > sum) continue;
                              
            //狀態不可達或者使用王的數量超過k
                
                              
            if(!contradict(s1,s2)) { //狀態不沖突
                                  f[i][s1][c1+c2] += f[i-1][s2][c2];
                              }
                          }
                      }
                  }
              }
              LL res 
            = 0;
              
            for(i = 0;i <= full;i++) {
                  res 
            += f[n][i][sum];
              }
              cout 
            << res << endl;

              
            return 0;
            }


             

            posted on 2010-01-13 22:39 schindlerlee 閱讀(1134) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告

            亚洲精品tv久久久久久久久久| 人妻无码久久精品| 中文字幕无码免费久久| 亚洲人AV永久一区二区三区久久| 久久免费视频1| 欧美熟妇另类久久久久久不卡| 波多野结衣中文字幕久久| 色成年激情久久综合| 久久伊人亚洲AV无码网站| 久久SE精品一区二区| 久久精品国产亚洲77777| 精品久久人人爽天天玩人人妻| 久久久久久久女国产乱让韩| 亚洲精品无码久久久影院相关影片| 69国产成人综合久久精品| 久久久这里只有精品加勒比| 国产成人久久激情91| 久久精品亚洲AV久久久无码| 88久久精品无码一区二区毛片| 欧美成a人片免费看久久| 97久久超碰成人精品网站| 成人综合久久精品色婷婷| 日本久久久久久中文字幕| 久久亚洲春色中文字幕久久久| 久久影院久久香蕉国产线看观看| 久久亚洲AV成人无码国产 | 久久激情亚洲精品无码?V| 久久久久久久女国产乱让韩| 91精品婷婷国产综合久久| 区久久AAA片69亚洲 | 久久久受www免费人成| 国产精品99精品久久免费| 久久这里只有精品18| 色青青草原桃花久久综合| 亚洲精品无码专区久久同性男| 国产国产成人久久精品| 色噜噜狠狠先锋影音久久| 久久精品成人免费网站| 精品精品国产自在久久高清 | 亚洲精品97久久中文字幕无码| 亚洲成色999久久网站|