P9339 题解

· · 题解

以下设 \sum a_i=s，同时认为 n,m,s 同级。

首先发现盒子和饼干之间是类似匹配的关系，因此我们以盒子为左部点，每种饼干为右部点，连边即为完全二分图，代表每种饼干只能装到每个盒子中一个。题目所求即为最少的左部点数量使得该图有完美匹配，输出方案。

完美匹配考虑霍尔定理，首先要 \sum b=\sum a，然后要求对于所有左部点集合 S，都满足 \sum_{i\in S}b_i\le\sum_{j=1}^n\min(a_j,\left|S\right|)，这里要对 a_j 取最小值是因为这种饼干最多只能贡献 a_j 的出度。

我们注意到等式右边的取值只与集合大小有关，可以对 a 排序后预处理固定集合大小下的上界 c。此时只要 b 最大的若干个的和不超过上界，则更小的一定也不超过，必然合法。问题转化为在 b 中可重复地选尽可能少的数，要求和为 s，同时保证前 i 大之和不超过 c_i。

直接使用背包，先对 b 排序，设 f_{i,j,k} 表示考虑了前 i 大的 b，选了 j 个，总和为 k 是否可行，对所有 k>c_j 的状态强制赋成 0 即可保证限制，转移是完全背包，为 f_{i,j,k}=f_{i-1,j,k} \vee f_{i,j-1,k-b_i}，这样就是 O(n^3) 的。

但是我们注意到在 f_{i,j,k} 中使用的 b 至少是 b_i，因此 j\le \lfloor\frac s {b_i}\rfloor。又因为 b_i 两两不同，所以所有 j 的个数和不超过 O(n\ln n)，复杂度降为 O(n^2\ln n)。又注意到 DP 值是 0 或 1，同时 f_{i,j} 只会从 f_{i-1,j} 和 f_{i,j-1} 在 k 这一维以相同的偏移量转移，因此可以把 f_{i,j} 在 k 这一维的 s 个状态压到 bitset 里优化转移，最终复杂度为 O(\frac{n^2\ln n}w)。

至于输出方案，先在 DP 数组上倒着把 b 的方案找出来，然后每次贪心地把 a 最大的若干种各放一个在该盒子里并减 1，用堆维护这个过程即可，具体看下面代码。值得一提的是，如果没有方案要求，上面的 DP 其实是可以滚动数组优化的。

#include<iostream>
#include<algorithm>
#include<bitset>
#include<queue>
#define bs bitset <N>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=15000+10;
int n,m,s,r=-1,a[N],b[N],p[N],c[N],w[N];
bool cmpa(int x,int y) {return a[x]<a[y];}
bool cmp(int x,int y) {return x>y;}
bs lm[N];
vector <bs> f[N];
vector <pii> tv;
priority_queue <pii> q;
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],s+=a[i],p[i]=i;
    cin>>m;
    for(int i=1;i<=m;i++) cin>>b[i];
    sort(p+1,p+1+n,cmpa),sort(b+1,b+1+m,cmp);
    int tp=0,ts=0;
    for(int i=1;i<=s;i++)
    {
        while(tp<n&&a[p[tp+1]]<=i) tp++,ts+=a[p[tp]];
        c[i]=ts+(n-tp)*i;
    }
    b[0]=s+1,lm[0][0]=1;
    for(int i=1;i<=s;i++) lm[i]=lm[i-1],lm[i][i]=1;
    for(int i=0;i<=m;i++) f[i].resize(s/b[i]+1);
    f[0][0][0]=1;
    for(int i=1;i<=m;i++) for(int j=0;j<=s/b[i];j++)
    {
        if(j<=s/b[i-1]) f[i][j]=f[i-1][j];
        if(j) f[i][j]|=(f[i][j-1]<<b[i]);
        f[i][j]&=lm[c[j]];
    }
    for(int i=1;i<=s/b[m];i++) if(f[m][i][s]) {r=i; break;}
    cout<<r<<'\n';
    if(r==-1) return 0;
    int cur=s,tw=m;
    for(int i=1;i<=r;i++) for(int j=tw;j>=1;j--) 
        if(f[j][r-i+1][cur]&&f[j][r-i][cur-b[j]])
            {w[i]=b[j],cur-=b[j],tw=j; break;}
    for(int i=1;i<=n;i++) q.push({a[i],i});
    for(int i=1;i<=r;i++)
    {
        cout<<w[i]<<' ',tv.clear();
        for(int j=0;j<w[i];j++)
        {
            pii te=q.top(); q.pop();
            te.fi--,cout<<te.se<<' ';
            if(te.fi) tv.push_back(te);
        }
        for(pii te:tv) q.push(te);
        cout<<'\n';
    }
    return 0;
}