<output id="qn6qe"></output>

    1. <output id="qn6qe"><tt id="qn6qe"></tt></output>
    2. <strike id="qn6qe"></strike>

      亚洲 日本 欧洲 欧美 视频,日韩中文字幕有码av,一本一道av中文字幕无码,国产线播放免费人成视频播放,人妻少妇偷人无码视频,日夜啪啪一区二区三区,国产尤物精品自在拍视频首页,久热这里只有精品12

      hdu1400/acwing 291 Mondriaan's Dream

      題意描述:

        給定一塊n*m的區域,用1*2的長方形填充,長方形可以橫著或豎著擺,問一共有多少種填充方案

      具體思路:  

       題意沒什么好說的,簡單易懂,很經典的一類狀態壓縮問題(在棋盤中求填充方案)。

       觀察數據,滿足n,m都比較小,但是搜索的復雜度大到無法接受,考慮使用狀態壓縮求解此類問題

       首先,肯定是第一步,即對題目給定的圖進行初始化,初始化應該怎么搞?觀察到若使用橫著填的方法填充一行的情況,發現有很多單行中有奇數數量的橫向填充方案完全不合法,考慮初始化。即預處理出合理的情況,用桶來記錄,稍后再篩選出合法的情況。

       第一步篩選完成了,雖然排除了許多冗余的情況,但是如此大的數據直接dp,兩個指數級別的數相乘會導致復雜度完全無法接受,所以考慮第二步初始化,即將本行的狀況與上一行進行比對,確定最終到底有幾個合法的情況。 

       最后一步進入正題,dp環節,dp環節和為什么這樣轉移在代碼中解釋

      代碼實現:

      #include<bits/stdc++.h>
      using namespace std;
      const int N=1<<13;
      long long dp[13][N],n,m;
      bool st[N];//桶數組判斷合法狀態
      vector<vector<long long> >G(N);//第二步篩選后的合法狀態
      int main()
      {
          while(cin>>n>>m,n||m)
          {
              for(int i=0;i<(1<<n);i++)
              {
                  int cnt=0;bool isvalid=true;//記錄當前有幾個0
                  for(int j=0;j<n;j++)
                  {
                      if((i>>j)&1)//取出當前為的值,如果當前位為一,之前的cnt記錄的"0"的個數清空,接著判斷當前狀態是否合法
                      {
                          if(cnt&1)//如果cnt為偶數,不合法
                          {
                              isvalid=false;
                              break;
                          }
                          cnt=0;//清空不清空差不多
                      }
                      else cnt++;//當前位為“0”,繼續累加
                  }
                  if(cnt&1) isvalid=false;//判斷最后一行是什么情況
                  st[i]=isvalid;
              }
              for(int j=0;j<(1<<n);j++)
              {
                  G[j].clear();//初始化
                  for(int k=0;k<(1<<n);k++)
                  {
                //細說st[j|k],關鍵至極
                //首先,j&k是判斷是否是上一行是"1",下一行是"0",因為不是這樣就不合法,簡言之,只要j&k==1就不合法
                //再就是st[j|k]
                //首先要了解一點,就是k枚舉的是上一行的所有狀態,所以st[j|k]是什么意思呢
                //明確,st存的是所有合法的狀態,如果j|k它不是一個合法的狀態,即此時會有奇數個零,那么實際上這個狀態它是不合法的,即上一行伸長下來和這一行伸長下去的,這些被伸長或者伸長下去的
                //是不能供橫著放的格子放的
                //所以要這樣
      if((j&k)==0&&st[j|k]) { G[j].push_back(k); } } } memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=m;i++) { for(int j=0;j<(1<<n);j++) { for(auto k:G[j]) { dp[i][j]+=dp[i-1][k];//當前行的狀態的答案是上一行所有可能情況的和 } } } cout<<dp[m][0]<<endl;//答案就是已經填到m行,且當前行沒有向下伸長的情況 } return 0; }

       

      posted @ 2023-09-11 22:11  Noname_min  閱讀(30)  評論(0)    收藏  舉報
      主站蜘蛛池模板: 国产成人AV男人的天堂| 国产精品一区二区中文| 视频一区二区三区刚刚碰| 精品粉嫩国产一区二区三区| 亚洲av色香蕉一区二区三区精品| 丁香婷婷激情综合俺也去| 青草草97久热精品视频| 国产精品推荐视频一区二区| 亚欧乱色国产精品免费九库| 精品亚洲国产成人av| 成人免费在线播放av| 久久人与动人物a级毛片 | 人妻熟女一二三区夜夜爱| 深夜释放自己在线观看| 凸凹人妻人人澡人人添| 一级女性全黄久久片免费| 亚洲成在人线在线播放无码| 在线观看潮喷失禁大喷水无码| 亚洲av日韩av中文高清性色| 熟妇人妻中文a∨无码| 婷婷精品国产亚洲av在线观看 | 天天综合色一区二区三区| 香港日本三级亚洲三级| 人人澡人摸人人添| 亚洲国产码专区在线观看| 四虎永久免费很黄的视频| 亚洲国产欧美一区二区好看电影| 麻豆蜜桃av蜜臀av色欲av | 国产亚洲精品俞拍视频| 成全我在线观看免费第二季| 亚洲欧美日韩愉拍自拍美利坚| 亚洲最大av资源站无码av网址| 非会员区试看120秒6次| 亚洲综合网中文字幕在线| yyyy在线在片| 中文无码乱人伦中文视频在线| 久久精品麻豆日日躁夜夜躁| 亚洲av日韩av永久无码电影| 18女下面流水不遮图| 伊人久久大香线蕉av色婷婷色| 久久精品国产99国产精品澳门|