UVa 12235 - Help Bubu | Sengxian's Blog

UVa 12235 - Help Bubu

#动态规划 #状态压缩动态规划

Published on 2016-10-23

描述

有 $n(n\le 100)$ 本放在书架上，高度分别为，定义的混乱值为权值的段数，现在你可以将 $k(k\le 100)$ 本书拿出来，放在书中间的任意一个位置（不改变其余书的顺序），请问最终能得到的最小混乱值是多少？

分析

第一眼看上去本题不好做，但是我们发现这个题的限制其实是很松的，书的段的顺序其实没有关系，只需要知道最后一段是谁就行了。而且这个题权值只有 8 种情况，这启发我们进行状压 DP：设 $dp[i][j][k][s]$ 为在前 $i$ 本书中拿走 $k$ 本书，剩下排在最后的一本书是 $j$ ，剩下的书的权值状况为 $s$ 的最小混乱值。
状态转移采用刷表转移，分为拿走 $i + 1$ 这本书和不拿走 $i + 1$ 这本书，拿走的书就不管了，不拿走的书要计算答案，详情参见代码。注意 $s = 0$ 表示现在没有书留下，这时候最后一个是谁是没有意义的，所以要判一下。

上述 DP 中我们对拿走的书没有进行处理，我们把它留到最后，对于最终状态 $dp[n][j][k][s]$ ，不妨设 $A$ 为全体权值的集合，那么这个状态最后的答案为 $\vert A\backslash s\vert$ ，原因是对于 $s$ 中有的权值，那么拿走的书中是这个权值的可以直接插入，不增加混乱值；而对于没有的权值，拿走的书中是这个权值的就必须新开辟一个段，增加 1 的混乱值。

总结：本题 DP 不难想到，重要的是拿走的书不当时处理，而是最后一起处理，这样就可以处理拿走的书放在后面的情况，避免漏掉最优解。

代码

//  Created by Sengxian on 2016/10/21.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  UVa 12235 状压 DP
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 100 + 3, MAX_K = 100 + 3, MAX_V = 8;
int n, K, a[MAX_N], dp[2][MAX_V][MAX_K][1 << MAX_V];

inline void tension(int &a, const int &b) {
    if (b < a) a = b;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    int caseNum = 0;
    while (n = ReadInt(), K = ReadInt(), n + K) {
        int ALL = 0;
        for (int i = 0; i < n; ++i) a[i] = ReadInt() - 25, ALL |= 1 << a[i];
        memset(dp[0], 0x3f, sizeof dp[0]);
        dp[0][a[0]][0][1 << a[0]] = 1;
        dp[0][0][1][0] = 0;
        int cur = 0;
        for (int i = 0; i < n - 1; ++i, cur ^= 1) {
            memset(dp[!cur], 0x3f, sizeof dp[!cur]);
            for (int s = 0; s < (1 << MAX_V); ++s)
                for (int j = 0; j < MAX_V; ++j)
                    for (int k = 0; k <= K; ++k) if (dp[cur][j][k][s] != 0x3f3f3f3f) {
                        if (j == a[i + 1] && s) tension(dp[!cur][j][k][s], dp[cur][j][k][s]);
                        else {
                            tension(dp[!cur][j][k + 1][s], dp[cur][j][k][s]);
                            tension(dp[!cur][a[i + 1]][k][s | (1 << a[i + 1])], dp[cur][j][k][s] + 1);
                        }
                    }
        }
        int ans = INT_MAX;
        for (int s = 0; s < (1 << MAX_V); ++s)
            for (int j = 0; j < MAX_V; ++j)
                for (int k = 0; k <= K; ++k)
                    tension(ans, dp[cur][j][k][s] + __builtin_popcount(ALL ^ s));
        printf("Case %d: %d\n\n", ++caseNum, ans);
    }
    return 0;
}

UVa 1372 - Log Jumping BZOJ 3100 - 排列