• <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月14日星期四.pku3254 狀態壓縮動態規劃

            2010年1月14日星期四.pku3254 狀態壓縮動態規劃

            pku3254:狀態壓縮動態規劃
            題目給出了一個m*n(m,n<=12)的矩陣,1代表此點可以放玉米,0代表不可放
            求 最后可能的放置方案有多少種?
            題目中給出了一個例子
            2 3
            1 1 1
            0 1 0
            對于這個例子,放置的方法一共有9種

            這個題相對于1185 炮兵陣地來說要好做一些,只要記錄上一行的狀態,就可以了,不用記錄
            上上行的狀態。

            方法也是先枚舉出一行中的所有可行狀態。
            然后根據這些可行狀態按行遞推,中間還要記得判斷狀態是否和地形不沖突。
            注意運算符的優先級,按照以下形式寫成的宏定義會比較安全


            #define bin(i) (1 << (i))
            #define L(i) ((i) << 1)
            #define R(i) ((i) >> 1)

            const int N = 13;
            int f[N][bin(N)];
            int full,s[bin(N)],top,m,n,terrain[N];

            bool contradict(int x)
            {
              
            return x & L(x);
            }

            bool sameRow(int a,int b)
            {
              
            return (a&b);
            }

            void preproc()
            {
              
            int i;
              
            for(i = 0;i <= full;i++) {
                  
            if(!contradict(i)) {
                      s[top
            ++= i;
                  }
              }
            }

            int main()
            {
              
            int i,j,k;
              scanf(
            "%d%d",&n,&m);
              memset(f,
            0,sizeof(f));
              full 
            = bin(m) - 1;
              preproc();
              
            for (i = 1;i <= n;i++) {
                  
            int tmp = 0;
                  
            for (j = 1;j <= m;j++) {
                      scanf(
            "%d",&k);
                      tmp 
            = L(tmp) + (1 - k);
                  }
                  terrain[i] 
            = tmp;
              }
              f[
            0][0= 1;
              
            for(i = 1;i <= n;i++) {
                  
            for(j = 0;j < top;j++) {
                      
            if(s[j] & terrain[i]) continue;
                      
            for(k = 0;k < top;k++) {
                          
            if(!sameRow(s[j],s[k])) {
                              f[i][j] 
            =(f[i][j] +  f[i-1][k])%100000000;
                          }
                      }
                  }
              }
            //http://www.shnenglu.com/schindlerlee
              
            int res = 0;
              
            for(i = 0;i < top;i++) {
                  res 
            =(res + f[n][i])%100000000;
              }
              cout 
            << res << endl;
              
            return 0;
            }


            posted on 2010-01-14 15:00 schindlerlee 閱讀(1525) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告

            久久A级毛片免费观看| 伊人久久成人成综合网222| 亚洲成av人片不卡无码久久| 久久久久综合中文字幕| 久久人人爽人人爽人人爽| 久久天天躁狠狠躁夜夜不卡 | 久久精品国产一区二区三区| 久久久久久久综合日本| 久久精品国产亚洲av麻豆图片 | 99久久er这里只有精品18| 污污内射久久一区二区欧美日韩| 四虎国产精品成人免费久久| 亚洲αv久久久噜噜噜噜噜| 久久97久久97精品免视看| 久久人人爽人人爽人人爽| 精品999久久久久久中文字幕| 久久夜色精品国产噜噜亚洲a| 99精品久久精品一区二区| 国产精品成人无码久久久久久| 久久久噜噜噜www成人网| 精品久久久久久无码免费| 欧美一区二区三区久久综合| 久久热这里只有精品在线观看| AV色综合久久天堂AV色综合在 | 国产成人久久精品激情| 性做久久久久久久久久久| 伊人久久综合热线大杳蕉下载| 国产产无码乱码精品久久鸭| 伊人久久大香线蕉综合网站| 99久久精品免费| 久久午夜电影网| 久久影院久久香蕉国产线看观看| 69久久精品无码一区二区| 日日噜噜夜夜狠狠久久丁香五月| 久久亚洲精品无码播放| 四虎国产精品免费久久久| 狠狠色丁香久久婷婷综合五月| 日韩久久久久久中文人妻| 伊人久久综合成人网| 99麻豆久久久国产精品免费| 久久天天躁狠狠躁夜夜网站|