P9339 [JOIST 2023] 曲奇 / Cookies 题解

首先可以发现，假如知道了最终盒子的数量以及各自的大小，求出一组方案是容易的。贪心地从剩余最多的一种饼干中选一个放进盒子，只要盒子的分布是合法的，这样也必然能求出一组合法解。

只需求出盒子的分布即可。

把饼干放进盒子的过程抽象成二分图匹配。二分图的左部点是饼干，右部点是盒子，每一对左部点和右部点之间都有边，边权为 \(1\)。由 Hall 定理，任意提取一个右部点集合 \(S\)，都有 \(\sum_{i\in S}c_i\le\sum_{i=1}^n\min(a_i,|S|)\)。这里比较厉害。然后注意到，只要让盒子的大小降序排序，那么前 \(|S|\) 个 \(c_i\) 是上述限制的最严格情况。

然后就可以 DP，考虑可行性 DP。设 \(f_{i,j,k}\) 表示考虑了前 \(i\) 种盒子大小，开了 \(j\) 个盒子，当前总和为 \(k\) 的可行性。初始 \(f_{0,0,0}=1\)。转移有

\[f_{i,j,k}\gets f_{i-1,j,k}\lor f_{i,j-1,k-b_i} \]

首先 \(b_i\times j\le V\)，所以第二维实际上只有 \(\log n\) 级别。然后第三维用 bitset 优化，总复杂度 \(O(\frac{n^2\log n}w)\)。

#include<bits/stdc++.h>
#define il inline
using namespace std;

constexpr int MAXN=15005;
int n,a[MAXN],m,b[MAXN],V,sm[MAXN];
bitset<MAXN>msk[MAXN];
vector<bitset<MAXN>>f[MAXN];
int c[MAXN];
il void dfs(int i,int j,int k){
	if(!i||!j||!k) return;
	if(k>=b[i]&&f[i][j-1][k-b[i]]) c[j]=b[i],dfs(i,j-1,k-b[i]);
	else dfs(i-1,j,k);
}

int main(){
	cin.tie(nullptr)->sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		V+=a[i];
		for(int j=1;j<=a[i];j++) sm[j]++;
	}
	partial_sum(sm+1,sm+V+1,sm+1);
	cin>>m;
	for(int i=1;i<=m;i++) cin>>b[i];
	reverse(b+1,b+m+1);
	msk[0].set(0);
	for(int i=1;i<=V;i++){
		msk[i]=msk[i-1]<<1;
		msk[i].set(0);
	}
	f[0].assign(1,1);
	b[0]=V+1;
	for(int i=1;i<=m;i++){
		f[i].resize(V/b[i]+1);
		for(int j=0;j<=V/b[i];j++){
			bitset<MAXN>tmp;
			if(b[i-1]*j<=V) tmp=f[i-1][j];
			if(j) tmp|=f[i][j-1]<<b[i];
			tmp&=msk[sm[j]];
			f[i][j]=move(tmp);
		}
	}
	int ans=-1;
	for(int j=0;j<=V/b[m];j++)
		if(f[m][j][V]){
			ans=j;
			break;
		}
	cout<<ans<<'\n';
	if(!~ans) return 0;
	dfs(m,ans,V);
	priority_queue<pair<int,int>>q1,q2;
	for(int i=1;i<=n;i++) q1.emplace(a[i],i);
	for(int i=1;i<=ans;i++){
		cout<<c[i]<<' ';
		while(c[i]--){
			auto p=q1.top();
			q1.pop();
			cout<<p.second<<' ';
			if(--p.first) q2.push(p);
		}
		cout<<'\n';
		while(!q2.empty()) q1.push(q2.top()),q2.pop();
	}
	return 0;
}