题解 P6228 【[BalticOI 2019 Day2]汤姆的餐厅】
StudyingFather
2020-04-02 19:04:31
显然当 $\exists i \in [1,N]$，满足 $A_i \lt K$ 的时候无解。
在排除这种情况后，我们考虑 DP。
我们将每个菜的时间分拆为两部分：基本时间和额外时间。基本时间为 $K$ 小时，每个参与这道菜制作的厨师最多可以向它贡献 $1$ 小时时间（这样就满足了至少 $K$ 个厨师参与制作的要求），同时一个厨师的工作时间中，最多有 $\min \{N,B_i\}$ 的时间可以贡献为基本时间。剩下的时间则是额外时间。
一个方案是合法的，当且仅当：
1. 总雇佣时间 $\geq \sum a_i$；
2. 所有厨师向基本时间的贡献 $\geq N \times K$（超过的部分可以自动并入额外时间中，注意对额外时间的分配没有任何限制）。
这是一个背包的模型。
设 $f_{i,j}$ 表示考虑前 $i$ 位厨师，总雇佣时间为 $j$ 时，最大的基本时间数。
对于每个状态，有两种决策：
1. 不选第 $i$ 名厨师，此时 $f_{i,j}=f_{i-1,j}$；
2. 选第 $i$ 名厨师，此时 $f_{i,j}=f_{i-1,j-B_i}+\min \{N,B_i\}$。
在两种决策中选最优的一种即可。
最终最小合法雇佣时间数就是满足 $f_{M,j} \geq N \times K$ 且 $j \geq \sum a_i$ 的最小的 $j$。
时间复杂度 $O(M\sum b_i)$，空间复杂度在滚动数组优化后可以做到 $O(\sum b_i)$，可以通过本题。
```cpp
// Problem : P6228 [BalticOI 2019 Day2]汤姆的餐厅
// Contest : Luogu Online Judge
// URL : https://www.luogu.com.cn/problem/P6228
// Author : StudyingFather
// Site : https://studyingfather.com
// Memory Limit : 250 MB
// Time Limit : 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int b[305],f[2][90005];
int main()
{
int n,m,k,suma=0,sumb=0;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(x<k)
{
cout<<"Impossible"<<endl;
return 0;
}
suma+=x;
}
for(int i=1;i<=m;i++)
cin>>b[i];
memset(f,191,sizeof(f));
f[0][0]=0;
for(int i=1;i<=m;i++)
{
int p=i&1,q=p^1;
for(int j=0;j<b[i];j++)
f[p][j]=f[q][j];//这种情况下只能选决策一
sumb+=b[i];
for(int j=b[i];j<=sumb;j++)
f[p][j]=max(f[q][j],f[q][j-b[i]]+min(b[i],n));
}
for(int i=suma;i<=sumb;i++)
if(f[m&1][i]>=n*k)
{
cout<<i-suma<<endl;
return 0;
}
cout<<"Impossible"<<endl;
return 0;
}
```