Studying Father's luogu blog

Focus on interest!

题解 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;
}

2020-04-02 19:04:31 in 题解