题解：P9294 [POI 2020] Cukiernia / 糕点店

P9294 [POI 2020] Cukiernia / 糕点店

每个货架上有多个货物，目标是通过移动让每个货架上只有一个，每一次移动可以改变一个糕点的位置。

货架上有没有某一种糕点非常重要，而这个不容易通过维护 实现，因为上一个货架选择保留哪一种会影响到这一层要处理哪些糕点以及其个数。这个时候可以考虑用二进制的方法去处理有或没有的组合情况：一个二进制数的前三位分别表示是否有 这样遍历 就可以处理出所有可能的情况。

也就是说 表示的是第 个货架上，面对 情况，将整理好的状态转移给下一状态的最小代价。然后思考如何转移。假设 对应 。

的情况有些糕点可能是没有的，所以这个情况只有可能是其子情况推演过来。也就是说，如果 层的状态 拥有 没有的糕点并传递给了下一层 ，那么此时 层的状态不可能是 ，所以就有如下的推导：

• 可以是上一层货架和这一层的情况是完全一致的。
• 可以是上一层货架比这一层少了某一个，其有无糕点的其情况是当前情况的子情况。

那么对于现在我有某一种（以 为例），所以我想丢弃我现在拥有的 ，所以上一层的情况中，其他一样，仅仅是 的存在性不同，则并不影响可行性，所以就在其中选择最优。

我们对于每一种情况都进行这样的讨论，就可以推出状态转移了，具体见代码。同时可以使用滚动数组进行空间优化。毕竟只依赖上一层，而且是交叉依赖，所以保留两层完整的数组就足够了。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

const ll MAXN = 300005;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll n, d[MAXN], p[MAXN], r[MAXN];
ll type, f[2][8];

void in() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%lld%lld%lld", &d[i], &p[i], &r[i]);
    for (int i = 1; i <= n && type != 7; ++i) {
        if (d[i])	type |= 1;
        if (p[i])	type |= 2;
        if (r[i])	type |= 4;
    }
    return;
}
void dp() {
    for (int i = 0; i < 8; ++i)
        f[0][i] = f[1][i] = INF;
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        ll cur = i % 2, pre = (i - 1) % 2, tot = d[i] + p[i] + r[i];
        for (int j = 0; j < 8; ++j) {
            f[cur][j] = INF;
            if (j & 1)
                f[cur][j] = min(f[cur][j], min(f[pre][j], f[pre][j ^ 1]) + tot - d[i]);
            if (j & 2)
                f[cur][j] = min(f[cur][j], min(f[pre][j], f[pre][j ^ 2]) + tot - p[i]);
            if (j & 4)
                f[cur][j] = min(f[cur][j], min(f[pre][j], f[pre][j ^ 4]) + tot - r[i]);
        }
    }
    return;
}

int main() {
    in();
    dp();
    cout << f[n % 2][type];
    return 0;
}