自动搬运

查看原文

来自洛谷，原作者为

	StudyingFather 在纷繁杂乱的世界里，独自寻找属于自己的光荣与梦想。

搬运于2025-08-24 22:18:47，当前版本为作者最后更新于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)$，可以通过本题。

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