题解 P6228 【[BalticOI 2019 Day2]汤姆的餐厅】

· · 题解

显然当 \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;
}