「题解 P7098」yLOI2020 凉凉

November 30, 2020

2020   ·   OI   Chinese     ·   pre-university  

这题看到数据范围 $n\le 14$ 明示状压, 但是状压状态却相对难分析一点, 因为在思考爆搜策略时, 我们会发现, 不仅仅需要关心某一条线路或者某一个深度是否被选择, 同样也要关心哪条线路选择了哪个深度, 以便于不同线路之间合并的进行.

然而, 我们不妨考虑对阻碍状压的因素: 合并, 进行预处理, 将全部可以合并的线路 (即放在同一层不会发生冲突) 提前合并, 那么就变成了两个分别处理的基础状压 $dp$ 问题了.

合并的思路:

令 $d_{i,set}$ 表示 $set$ 集合内的所有列车放在第 $i$ 层所需的费用, 容易得到状压策略:

若新加入的列车 $j$ 与原集合 $set$ 不冲突, 即可进行状态转移:

$d_{i,set\bigcup{j}}=min{d_{i,set\bigcup{j}},d_{i,set}+sum_{j,i}}$

状压 $dp$ 的思路:

令 $f_{i,set}$ 表示 $set$ 集合内所有列车放在前 $i$ 层所需的费用, 那么我们就可以直接枚举子集来做了:

对于第$i$层每个可选的列车集合 $j$, 枚举它的子集 $k$, 令 $l=\complement_jk$, 则可以进行状态转移:

$f_{i,j} = min{f_{i,j}, f_{i-1,l} + d[i][k]}$

最后$ans=f_{i,U}$

当然, 由于状压 $dp$ 中 $4^n$ 的复杂度仍然无法接受, 所以还要用个枚举子集的 trick

for (int k = j; k; k = j & (k - 1))

这样时间复杂度就会降为 $n \times \Sigma_{i=0}^{n} C_n^i\times 2^i\times 1^{n-i}=n\times 3^n$ 了

完整代码:

(记得开long long)

#include <bits/stdc++.h>

#define int long long

using namespace std;

typedef long long ll;

const int MAXN = 16;
const int MAXS = 1 << 16;
const int MAXM = 1e5 + 5;

int n, m;
int siz[MAXN];
bitset<MAXM> sta[MAXN];
int price[MAXN][MAXM], data[MAXN][MAXM];

// sum[i][j] refer to the price of constructing all the stations for train j at the height i
int sum[MAXN][MAXN];
// d[i][j] refer to the price of constructing all the stations for trains in set(j) at the height i
int d[MAXN][MAXS];
// f[i][j] refer to the price of constructing all the stations for trains in set(j) beyond or at height i
int f[MAXN][MAXS];

signed main()
{
    memset(d, 0x3f, sizeof(d));
    memset(f, 0x3f, sizeof(f));
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        d[i][0] = 0;
        for (int j = 1; j <= m; j++)
            scanf("%lld", &price[i][j]);
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &siz[i]);
        for (int j = 1; j <= siz[i]; j++)
        {
            scanf("%lld", &data[i][j]);
            sta[i].set(data[i][j]);
        }
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= siz[i]; k++)
                sum[j][i] += price[j][data[i][k]];
        }
    }
    int maxt = 1 << n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < maxt; j++)
        {
            if (d[i][j] > 1e15)
                continue;
            bitset<MAXM> now;
            now.reset();
            for (int k = 0; k < n; k++)
                if ((j >> k) & 1)
                    now |= sta[k];
            for (int k = 0; k < n; k++)
            {
                if (!((j >> k) & 1) && !(now & sta[k]).count())
                {
                    int nex = j | (1 << k);
                    d[i][nex] = min(d[i][nex], d[i][j] + sum[i][k]);
                }
            }
        }
    }
    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < maxt; j++)
        {
            f[i][j] = f[i - 1][j];
            for (int k = j; k; k = j & (k - 1))
            {
                int res = j ^ k;
                f[i][j] = min(f[i][j], f[i - 1][res] + d[i][k]);
            }
        }
    }
    printf("%lld", f[n][maxt - 1]);
    return 0;
}