UVA Live Archive 4490 Help Bubu（状压dp）

难点在于状态设计，从左向右一本书一本书的考虑，每本书的决策有两种拿走或者留下，

对于拿走后的书，之后要放回，但是决策过程中不知道到往哪里放，

虽然前面的书的种类确定，可能是往后面放更优，而后面的书的类型还不确定。对于所有拿出来的书，最后会增加多少段只和书的种类有关。

所以我们用s记录留下书的种类，等到所有书都考虑完了以后一并放回。

对于留下的书，是否成为新的一段和上一次书的高度有关，因此用一个last记录上一次书的种类。（用s来判断一下last不存在的情况）

dp[i = 第i本书][j = 拿了j次][s = 剩下书的种类][last = 上一次书的种类] = 最小混乱度

转移方程见代码

直接for是最好写的

#include<bits/stdc++.h>

using namespace std;

const int maxn = , maxs = <<;

int dp[][maxn][maxs][];

int bc[maxs];

int h[maxn];

const int INF = 0x3f3f3f3f;

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    for(int i = maxs; i-- ;){

        int x = i;

        while(x){;

            bc[i] += x&;

            x >>= ;

        }

    }

    int ks = , n, k;

    while(scanf("%d%d",&n,&k),n+k){

        int All = ;

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

            scanf("%d",h+i);

            h[i] -= ;

            All |= <<h[i];

        }

        memset(dp[],0x3f,sizeof(dp[]));

        dp[][][<<h[]][h[]] = ;

        dp[][][][] = ;

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

            int a = i&, b = a^, bs = <<h[i];

            memset(dp[a],0x3f,sizeof(dp[a]));

            for(int j = k; j >= ; j--){

                for(int s = maxs; s--; ){

                    for(int ls = ; ls--; ){

                        if(dp[b][j][s][ls] < INF){

                            dp[a][j][s|bs][h[i]] = min(dp[a][j][s|bs][h[i]], dp[b][j][s][ls] + (s?( h[i] == ls?: ):));

                            if(j < k) dp[a][j+][s][ls] = min(dp[a][j+][s][ls], dp[b][j][s][ls]);

                        }

                    }

                }

            }

        }

        int a = n&^;

        int ans = n+;

        for(int s = maxs; s--;){

            for(int ls = ; ls--; ){

                ans = min(ans, dp[a][k][s][ls] + bc[All^s]);

            }

        }

        printf("Case %d: %d\n\n",++ks,ans);

    }

    return ;

}

实际上可能有很多状态访问不到的时候，for会枚举到一些无用的状态，这时候可以考虑把有效的状态保存下来，（记忆化搜索也可以避免访问无用状态，但是没办法用滚动数组了）

这样的话不需要对整个dp数组初始化，取代的是需要状态判重。

这样写有种做搜索题的感觉。

#include<bits/stdc++.h>

using namespace std;

const int maxn = , maxs = <<;

int dp[][maxn][][maxs];

int vis[maxn][][maxs],clk;

int h[maxn];

const int nil = ;

struct state

{

    int ct,ls,s;

}vc[][maxn**maxs];

int sz[];

#define dim(x) [x.ct][x.ls][x.s]

#define add(id,ct,ls,s) vc[id][sz[id]++] = state{ct,ls,s};

#define psb(id) vc[id][sz[id]++] = y;

#define clr(id) sz[id] = 0;

#define edof(id) vc[id][sz[id]]

#define updata(v)\

if(vis Td != clk){\

    vis Td = clk;\

    dp[a] Td = v;\

    psb(a);\

}else {\

    dp[a] Td = min(dp[a] Td, v);\

}

inline int bc(int x)

{

    int re = ;

    while(x){

        re += x&;

        x >>= ;

    }

    return re;

}

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    int ks = , n, k;

    while(scanf("%d%d",&n,&k),n+k){

        int All = ;

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

            scanf("%d",h+i);

            h[i] -= ;

            All |= <<h[i];

        }

        clr();

        state y = {,h[],<<h[]};

        dp[] dim(y) = ;

        psb()

        y = {,nil,};

        dp[] dim(y) = ;

        psb()

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

            int a = i&, b = a^, bs = <<h[i];

            clr(a)

            clk++;

            for(int j = ; j < sz[b]; j++){

                auto &x = vc[b][j];

                int val = dp[b] dim(x);

                int tmp = val + ( x.s? ( (x.ls == h[i])?: ) :  );

                y = {x.ct,h[i],x.s|bs};

                #define Td [y.ct][y.ls][y.s]

                updata(tmp)

                if(x.ct < k){

                    y = {x.ct+, x.ls, x.s};

                    updata(val)

                }

            }

        }

        int a = n&^;

        int ans = n+;

        for(int j = ; j < sz[a]; j++){

            auto &x = vc[a][j];

            ans = min(ans, dp[a] dim(x) + bc(All^x.s));

        }

        printf("Case %d: %d\n\n",++ks,ans);

    }

    return ;

}

巴特西

UVA Live Archive 4490 Help Bubu（状压dp）

最新文章

热门文章