dango

Hdu 3237 Help Bubu

题目描述：

    原题地址：http://acm.hdu.edu.cn/showproblem.php?pid=3237

    题目可以抽象成这样，有0~7这样8个数字组成的数字串，可以抽出k个数字再插回到任意位置，问最后不同的数字段（相同的数字组成一段，例如00077112有4段，000为一段，77为一段……）

题目分析：

    这个题乍一看很像动态规划，但是真的是动态规划，不过我还是第一次做这样的动态规划。

    参考了一位大牛的报告，地址如下：

F[i][j][k][s]，表示前i本书，拿走j本，留下的书最后一本高k（呃我觉得这个很巧妙），留下的书的组合为s（例如1010000表示高度为0的，高度为2的书有留下的）

    状态转移部分伪代码（当处理到f[i][j][k][s]时）

(1)  考虑第i本书不抽走，在f[i-1][j][k][s]存在的前提下（也就是处理到i-1本书的时候，这个状态下，留下的最后一本书高度为k）：

若这本书的高度也是k，那么这本书的加入不会造成混乱度的提升，则f[i][j][k][s] = min(f[i][j][k][s], f[i-1][j][k][s])

若这本书的高度不是k，那么这本书的加入会造成混乱度增加1，则f[i][j][k][s] = min(f[i][j][k][s], f[i-1][j][k][s] + 1)

（2）考虑抽走第i本书，f[now][j+1][k][s] = min( f[pre][j][k][s], f[now][j+1][k][s])

最后处理答案的时候要考虑一下那些被抽走的书还是要插回去的。如果有一本高度为h的书被抽走，剩下的书里头都没有高度为h的，那么混乱度需要增加。

代码：

hdu3237
#include <cstdio>
#include <cstdlib>

const int maxn = 101;
const int INF = 200;
const int total_s = 1<<8 + 1;

int f[2][maxn][9][total_s];
int n,take,all;
int h[maxn];

bool init(){
    int i,j,k,s;
    scanf("%d%d", &n, &take);
    if (n==0 && take==0) return false;
    all = 0;
    for (i=1; i<=n; i++){
        scanf("%d", &h[i]);
        h[i] -= 25;
        all |= (1<<h[i]);
    }
    
    return true;
}

int solve(){
    int i,j,k,s,temp,ans,now, pre;

    for (j=0; j<=take; j++)
        for (k=0; k<=8; k++)
            for (s=0; s<=1<<8; s++)
                f[0][j][k][s] = INF;
    f[0][0][8][0] = 0;

    for (i=1; i<=n; i++){
        
        now = i%2; pre = (i-1)%2;
        for (j=0; j<=take; j++)
            for (k=0; k<=8; k++)
                for (s=0; s<=1<<8; s++)
                    f[now][j][k][s] = INF;
                    
        for (j=0; j<=i && j<=take; j++)
            for (k=0; k<=8; k++)
                for (s=0; s<(1<<8); s++){
                    //save this one
                    if (f[pre][j][k][s]!=INF){
                        if (h[i] == k && f[pre][j][k][s] < f[now][j][k][s])
                            f[now][j][k][s] = f[pre][j][k][s];
                        if (h[i] != k && f[pre][j][k][s]+1 < f[now][j][h[i]][s|(1<<h[i])])
                            f[now][j][h[i]][s|(1<<h[i])] = f[pre][j][k][s]+1;
                    }
                    //get this one
                    if (j<take && f[pre][j][k][s]!= INF){
                        if (f[pre][j][k][s] < f[now][j+1][k][s])
                            f[now][j+1][k][s] = f[pre][j][k][s];
                    }
                }
    }
    ans = INF;
    int t = n%2;
    for (k=0; k<=8; k++)
        for (s=0; s<(1<<8); s++)
            if (f[t][take][k][s] != INF){
                temp = f[t][take][k][s];
                int temp_s = s;
                for (i=0; i<=7; i++)
                    if (((1<<i)&temp_s) == 0 && ((1<<i)&all) != 0){
                        ++temp;
                        temp_s = (1<<i) | s;
                    }
                if (temp<ans) ans = temp;
            }
    return ans;
}

int main(){
    int T(0);
    while (init()){
        int s = solve();
        printf("Case %d: %d\n\n", ++T, s);
    }
    return 0;
}