题解：P5997 [PA 2014] Pakowanie

· · 题解

思路

状压 dp 好题。

讲一下我的全部思路过程：

首先看范围大概是 O(n2^n) 的时间复杂度。m=100，我们考虑贪心，我们一定会尽量先填大包再填小包。于是排一遍序，设计状态 f_S 表示填完 S 集合，最少的使用包数。

考虑转移，比较容易想到对于 S，枚举 T 满足 T 与 S 没有交。然后看 T 体积和是否小于等于下一个包的体积。这样做需要枚举子集，时间复杂度 O(3^n)。显然跑不过去。

那么，我们想，对于一个集合，我们是否可以只枚举一个数，往下一个状态转移？答案是可行的。那么我们怎么知道现在能不能继续填下一个包？修改状态，多记录一个现在当前包还剩多少体积。显然，这个值与最小包数并不冲突，所以我们以最小包数为第一关键字尽量小，以剩余体积为第二关键字尽量大。做完了，详细细节见代码。

代码

#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define pll pair <ll, ll>
#define fi first
#define se second
#define y1 noip200

using namespace std;

const int N = 25, p = 1e9 + 7;

int n, m, a[26], b[115];
pair <int, int> f[1 << 25]; // 双关键字排序
// 这里为了省事，因为第二个关键字是越大越好，所以我存了负数

void init() {

}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];
    sort(b + 1, b + m + 1, greater <int> ()); // 从大到小
    b[m + 1] = 1 << 28;
    for (int S = 1; S < 1 << n; S++) 
        f[S] = {1 << 28, 1 << 28};
    for (int S = 0; S < 1 << n; S++) {
        if (f[S].fi > 114) continue; // 如果你 RE on #18, 无法转移到的状态也不要往下转移
        for (int i = 0; i < n; i++) 
            if ((S >> i & 1) ^ 1) {
                if (-f[S].se < a[i] && b[f[S].fi + 1] >= a[i]) // 没有空间，另开包
                    f[S | 1 << i] = min(f[S | 1 << i], {f[S].fi + 1, -(b[f[S].fi + 1] - a[i])});
                if (-f[S].se >= a[i]) // 还有空间，塞进去
                    f[S | 1 << i] = min(f[S | 1 << i], {f[S].fi, f[S].se + a[i]});
            }
    }
    if (f[(1 << n) - 1].fi > m) cout << "NIE\n"; // 无解
    else cout << f[(1 << n) - 1].fi << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    int t = 1;
    // scanf("%d", &t);
    while (t--) solve();
    return 0;
}

总结

  1. 看范围猜时间复杂度。
  2. 转移和状态并不是一成不变的，需要灵活改变。