亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

POJ1038 - Bugs Integrated, Inc.(狀態壓縮DP)

系統 1586 0

題目大意

要求你在N*M大小的主板上嵌入2*3大小的芯片,不能夠在損壞的格子放置,問最多能夠嵌入多少塊芯片?

題解

媽蛋,這道題折騰了好久,黑書上的講解看了好幾遍才稍微有點眉目(智商捉急),接著看了網上大牛的解題報告和實現代碼才弄明白怎么用三進制來進行狀態壓縮,關鍵就是理解能夠橫著放置和豎著放置的條件。由于豎著放置會受到前面兩行的影響,這樣我們就可以用三進制來表示前面兩行的狀態了,然后根據前面兩行的狀態我們也可以得到當前行與前一行的初始狀態,之后再根據兩個的狀態進行放置磚塊~~~~具體怎么樣的看黑書吧

代碼:

      #include <iostream>
      
        

#include 
      
      <cstdio>
      
        

#include 
      
      <cstring>
      
        

#include 
      
      <algorithm>


      
        using
      
      
        namespace
      
      
         std;


      
      
        #define
      
       MAXN 15


      
        int
      
       dp[
      
        2
      
      ][
      
        60000
      
      
        ],pre[MAXN],now[MAXN];


      
      
        int
      
       mp[MAXN*
      
        10
      
      +
      
        5
      
      
        ][MAXN];


      
      
        int
      
      
          s[MAXN],n,m;


      
      
        int
      
       To_ten(
      
        int
      
       *
      
        a)

{

    
      
      
        int
      
       ret=
      
        0
      
      
        ;

    
      
      
        for
      
      (
      
        int
      
       i=
      
        1
      
      ; i<=m; i++
      
        )

        ret
      
      +=a[i]*
      
        s[i];

    
      
      
        return
      
      
         ret;

}


      
      
        void
      
       To_three(
      
        int
      
       *a,
      
        int
      
      
         x)

{

    
      
      
        for
      
      (
      
        int
      
       i=
      
        1
      
      ; i<=m; i++
      
        )

    {

        a[i]
      
      =x%
      
        3
      
      
        ;

        x
      
      /=
      
        3
      
      
        ;

    }

}


      
      
        void
      
       dfs(
      
        int
      
       sum,
      
        int
      
       x,
      
        int
      
       y,
      
        int
      
      
         status)

{

    dp[x][status]
      
      =
      
        max(dp[x][status],sum);

    
      
      
        if
      
      (y>=m) 
      
        return
      
      
        ;

    
      
      
        if
      
      (!pre[y]&&!pre[y+
      
        1
      
      ]&&!now[y]&&!now[y+
      
        1
      
      
        ])

    {

        now[y]
      
      =
      
        2
      
      ,now[y+
      
        1
      
      ]=
      
        2
      
      
        ;

        
      
      
        int
      
       st=
      
        To_ten(now);

        dfs(sum
      
      +
      
        1
      
      ,x,y+
      
        2
      
      
        ,st);

        now[y]
      
      =
      
        0
      
      ,now[y+
      
        1
      
      ]=
      
        0
      
      
        ;

    }

    
      
      
        if
      
      ((y+
      
        2
      
      <=m)&&!now[y]&&!now[y+
      
        1
      
      ]&&!now[y+
      
        2
      
      
        ])

    {

        now[y]
      
      =
      
        2
      
      ,now[y+
      
        1
      
      ]=
      
        2
      
      ,now[y+
      
        2
      
      ]=
      
        2
      
      
        ;

        
      
      
        int
      
       st=
      
        To_ten(now);

        dfs(sum
      
      +
      
        1
      
      ,x,y+
      
        3
      
      
        ,st);

        now[y]
      
      =
      
        0
      
      ,now[y+
      
        1
      
      ]=
      
        0
      
      ,now[y+
      
        2
      
      ]=
      
        0
      
      
        ;

    }

    dfs(sum,x,y
      
      +
      
        1
      
      
        ,status);

}


      
      
        int
      
      
         main()

{

    
      
      
        int
      
      
         T;

    s[
      
      
        0
      
      ]=
      
        0
      
      ,s[
      
        1
      
      ]=
      
        1
      
      
        ;

    
      
      
        for
      
      (
      
        int
      
       i=
      
        2
      
      ; i<=
      
        12
      
      ; i++
      
        )

        s[i]
      
      =s[i-
      
        1
      
      ]*
      
        3
      
      
        ;

    scanf(
      
      
        "
      
      
        %d
      
      
        "
      
      ,&
      
        T);

    
      
      
        while
      
      (T--
      
        )

    {

        
      
      
        int
      
      
         k;

        scanf(
      
      
        "
      
      
        %d%d%d
      
      
        "
      
      ,&n,&m,&
      
        k);

        memset(dp,
      
      -
      
        1
      
      ,
      
        sizeof
      
      
        (dp));

        memset(mp,
      
      
        0
      
      ,
      
        sizeof
      
      
        (mp));

        
      
      
        while
      
      (k--
      
        )

        {

            
      
      
        int
      
      
         x,y;

            scanf(
      
      
        "
      
      
        %d%d
      
      
        "
      
      ,&x,&
      
        y);

            mp[x][y]
      
      =
      
        1
      
      
        ;

        }

        
      
      
        for
      
      (
      
        int
      
       i=
      
        1
      
      ; i<=m; i++
      
        )

            pre[i]
      
      =mp[
      
        1
      
      ][i]+
      
        1
      
      
        ;

        
      
      
        int
      
       temp=
      
        To_ten(pre);

        dp[
      
      
        0
      
      ][temp]=
      
        0
      
      
        ;

        
      
      
        for
      
      (
      
        int
      
       i=
      
        2
      
      ; i<=n; i++
      
        )

        {

            memset(dp[(i
      
      +
      
        1
      
      )&
      
        1
      
      ],-
      
        1
      
      ,
      
        sizeof
      
      (dp[(i+
      
        1
      
      )&
      
        1
      
      
        ]));

            
      
      
        for
      
      (
      
        int
      
       j=
      
        0
      
      ; j<s[m+
      
        1
      
      ]; j++
      
        )

                
      
      
        if
      
      (dp[i&
      
        1
      
      ][j]!=-
      
        1
      
      
        )

                {

                    To_three(pre,j);

                    
      
      
        for
      
      (
      
        int
      
       p=
      
        1
      
      ; p<=m; p++
      
        )

                        
      
      
        if
      
      
        (mp[i][p])

                            now[p]
      
      =
      
        2
      
      
        ;

                        
      
      
        else
      
      
        

                            now[p]
      
      =max(
      
        0
      
      ,pre[p]-
      
        1
      
      
        );

                    temp
      
      =
      
        To_ten(now);

                    dfs(dp[i
      
      &
      
        1
      
      ][j],(i+
      
        1
      
      )&
      
        1
      
      ,
      
        1
      
      
        ,temp);

                }

        }

        
      
      
        int
      
       ans=
      
        0
      
      
        ;

        
      
      
        for
      
      (
      
        int
      
       i=
      
        0
      
      ; i<s[m+
      
        1
      
      ]; i++
      
        )

            ans
      
      =max(ans,dp[(n+
      
        1
      
      )&
      
        1
      
      
        ][i]);

        printf(
      
      
        "
      
      
        %d\n
      
      
        "
      
      
        ,ans);

    }

    
      
      
        return
      
      
        0
      
      
        ;

}
      
    

POJ1038 - Bugs Integrated, Inc.(狀態壓縮DP)


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!?。?/p>

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 国产一区二区三区在线影院 | 欧美不卡视频 | 伊人五月天婷婷琪琪综合 | 综合网视频 | 天天操人人射 | 不卡的中文字幕 | 免费亚洲一区 | 国内精品久久久久影院一蜜桃 | 亚洲 欧美 成人日韩 | 亚洲区视频在线观看 | 亚洲图片欧美另类 | 久久九色综合九色99伊人 | 色婷婷中文字幕 | 在线人成精品免费视频 | 一区二区三区毛片免费 | 国产成人拍精品视频网 | 国产a网 | 欧美亚洲国产一区二区三区 | a毛片在线还看免费网站 | 国产羞羞视频在线播放 | 亚洲黄色高清视频 | 国产免费久久精品44 | 人人鲁免费播放视频人人香蕉 | 91在线丨亚洲 | 国产牛牛 | 日本高清一级做a爱过程免费视频 | 国产精品欧美一区二区 | 黄黄的网站在线观看 | 国产欧美一区二区三区精品 | 久久是免费只精品热在线 | 亚洲欧美中文日韩在线 | 91官网 | 久久澳门 | 亚洲国产人久久久成人精品网站 | 国产成人精品高清在线 | 欧美亚洲综合在线观看 | 久久草在线视频观看 | 337p欧美超大胆日本人术艺术 | 国产三级久久久精品三级 | 色网址在线 | 泰国理论片|