Petrozavodsk Winter-2018. Carnegie Mellon U Contest

D: Octagons

题目大意

八边形网格中，每个点连出的3条边分别标号a，b，c，一个八边形内的8条边最多2种标号，问给定一个经过边的标号序列，判断是否是一个闭合的环。

题解

我们可以发现，如果要成为一个闭合的环，至少会经过一个8边形上连续的5条边。比如abababab的八边形，必会经过ababa或者babab，这样等效于经过剩下的连续的三条边bab或者aba（对应）。这样可以缩短标号序列。

比如样例1的abababab等效于babbab，也就是bab 3条连续的边从左往右走再从右往左走。注意到中间的bb，是来回地重复经过了一条边，这样相当于不走b（仍能保持原来序列的闭合性）。所以我们删去bb也是等效的。那么babbab等效于baab等效于bb等效于空。因此abababab是闭合的。不空则不可能闭合。

#include <iostream>
#include <string>
using namespace std;

int main() {
    string str;
    cin >> str;

    for (int i = 0; str != ""; ++i) {
        if (i >= 1 && str[i] == str[i - 1]) {
            str.erase(i);
            str.erase(i - 1);
            i -= 2;
        } else if (i >= 4 && str[i] == str[i - 2] &&
            str[i - 2] == str[i - 4] && str[i - 1] == str[i - 3]) {
            str.erase(i);
            str.erase(i - 4);
            i -= 5;
        }
    }
    cout << (str == "" ? "closed" : "open");
    return 0;
}

H: Bin Packing

题目大意

给定$n(1\leq n\leq 24)$个物品，重量为$w_i$，装进一些容量为$S$的背包，最少需要多少个背包？

题解

注意到$n$很小。一开始一直在想dfs怎么写。。失败了。。
哪些物品放到一个背包里，可以转化为给定一个物品放置的序列，放满了一个背包就继续放下一个。问题是一样的。那么对于放置物品的顺序，状压dp就可以解决。
令$f[i]$表示状态为i时需要多少个背包，$g[i]$表示状态为i时最后一个背包装了多重。那么枚举状态和最后一个放置的物品即可。

#include <cstdio>
#include <utility>
using namespace std;

const int N = 24, NN = 1 << 24, inf = 0x3f3f3f3f;
pair<int, int> dp[NN];
int w[N];

int main() {
    int n, nn, S;
    scanf("%d%d", &n, &S);
    for (int i = 0; i < n; ++i)
        scanf("%d", &w[i]);
    nn = 1 << n;
    for (int i = 0; i < nn; ++i)
        dp[i] = make_pair(inf, 0);
    dp[0] = make_pair(0, S);

    for (int s = 0; s < nn; ++s)
        for (int j = 0; j < n; ++j)
            if (s & (1 << j)) {
                auto &s0 = dp[s ^ (1 << j)];
                pair<int, int> np;
                if (s0.second + w[j] <= S)
                    np = make_pair(s0.first, s0.second + w[j]);
                else
                    np = make_pair(s0.first + 1, w[j]);
                if (np < dp[s]) dp[s] = np;
            }
    printf("%d", dp[nn - 1].first);

    return 0;
}