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

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條評論
主站蜘蛛池模板: 91麻豆精品国产91久久久久 | 欧美精品福利在线视频 | 九九视频免费在线 | 青青久在线视频免费视频 | 午夜一级大片 | 日韩一区二区超清视频 | 亚洲国产免费 | 羞羞网站视频 | 手机看片日韩高清国产欧美 | 国产亚洲精品线观看77 | 色拍拍噜噜噜aⅴ在线观看 色拍拍欧美视频在线看 | 四虎avtom影院 | 最近手机中文字幕1页 | 天天操天天射天天爽 | 日韩精品在线一区 | 国内精品视频成人一区二区 | 免费看国产精品久久久久 | 欧美一级高清视频在线播放 | 精品欧美一区二区在线观看 | 亚洲国产一区二区a毛片 | 欧美日韩一卡二卡 | 亚洲精品国产综合一线久久 | 2022国内精品免费福利视频 | 国产综合精品久久亚洲 | 最新国产麻豆精品 | 国产三级久久久精品三级 | 久久在线视频 | 国产码欧美日韩高清综合一区 | www.日韩视频| 久热国产精品视频 | 熊出没之重启未来免费观看 | 久久精品免费观看 | 亚洲第一中文字幕 | 国产精品你懂的在线播放 | 欧美一级黄色毛片 | 亚洲精品人成无码中文毛片 | 日本中文在线三级在线播放 | 久草视频在线资源 | 亚洲国产爱久久全部精品 | 中文字幕在线最新在线不卡 | 超级毛片|