题解：P5997 [PA 2014] Pakowanie

思路

状压 dp 好题。

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

首先看范围大概是

O(n2^n)

的时间复杂度。

m=100

，我们考虑贪心，我们一定会尽量先填大包再填小包。于是排一遍序，设计状态

f_S

表示填完

S

集合，最少的使用包数。

考虑转移，比较容易想到对于

S

，枚举

T

满足

T

与

S

没有交。然后看

T

体积和是否小于等于下一个包的体积。这样做需要枚举子集，时间复杂度

O(3^n)

。显然跑不过去。

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

代码

CPP

#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;
}

总结

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

题解：P5997 [PA 2014] Pakowanie

文章操作

思路

代码

总结

相关推荐

评论

题解：P5997 [PA 2014] Pakowanie