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

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久久精品无码一区二区毛片 | aaaa视频| 久久久久久久久亚洲 | 免费的一级片网站 | 黄色成人在线网站 | 欧美vs日韩vs国产在线观看 | 欧美视频一区 | 四虎资源 | 久夜色精品国产一区二区三区 | 精品偷拍模特露出丝袜在线 | 日韩啊啊啊 | 国产91精品一区二区麻豆网站 | 国产精品96久久久久久久 | 亚洲一区二区三区高清 | 国产精品在线 | 中文字幕在线播放一区 | 特级毛片a级毛免费播放 | 好吊妞视频一区二区 | 久99久精品免费视频热77 | 成人免费毛片视频 | 亚洲国产精品乱码在线观看97 | 黄色成人免费网站 | 精品国精品国产自在久国产不卡 | 九九精品视频免费 | 色婷婷精品免费视频 | 欧美色插 | 国产成人福利夜色影视 | 欧美激情一区二区三级高清视频 | 欧美精品免费看 | 日本一级高清不卡视频在线 | 日韩国产中文字幕 | 天天拍拍夜夜出水 | 精品中文字幕一区二区三区四区 | 狠狠久久久久久亚洲综合网 | 婷婷四房 | 在线aa| 国产一区视频在线免费观看 | 日本一区二区三区中文字幕 |