Tom's Kitchen

Mamy do przygotowania $n$ potraw, $i$-ta wymaga co najmniej $a_i$ godzin pracy. Możemy zatrudnić $m$ kucharzy, $i$-ty będzie pracował co najwyżej $b_i$ godzin, ale musimy zapłacić mu dokładnie $b_i$. Nad każdą potrawą musi pracować co najmniej $k$ kucharzy.

Obliczyć minimalną ilość pieniędzy, którą musimy zapłacić za czas, w którym kucharze nie będą pracować.

Przypadek dla $k=1$

W podzadaniu 3 mamy $k=1$, czyli nie musimy się przejmować liczbą kucharzy przygotowujących potrawę, wystarczy, że $i$-tej z nich poświęcimy $a_i$ godzin. Zatem na wszystkie potrawy będziemy potrzebowali $A = \sum_{1\leq i\leq n} a_i$ godzin. Jeśli zatrudnimy podzbiór kucharzy $S$, to będą oni pracować $B_S = \sum_{i\in S} b_i$ godzin.

Tak więc wystarczy, żeby $B_S \geq A$, przy czym chcemy zminimalizować wartość $B_S - A$. Wykorzystamy tutaj rozwiązanie problemu plecakowego. Trzymamy tablicę $dp[0..B]$ dla $B = \sum_{1\leq i\leq m} b_i$. Analizujemy kolejnych kucharzy i chcemy, by po przeanalizowaniu $i$-tego był spełniony niezmiennik, że $dp[j] = 1$, jeśli istnieje podzbiór kucharzy $S \subseteq \{1,\ldots,i\}$, że $B_S = j$.

Na koniec odpowiedzią jest $j-A$ dla najmniejszego $j\geq A$, że $dp[j]=1$. Poniższy kod działa w złożoności czasowej $O(mB)$:

const int N = 310;
int n,m,k,a[N],b[N];
int dp[N*N],suma,sumb;

int main() {
  scanf("%d%d%d",&n,&m,&k);
  REP(i,n) scanf("%d",&a[i]);
  REP(i,m) scanf("%d",&b[i]);

  REP(i,n) suma += a[i];
  REP(i,m) sumb += b[i];
  
  dp[0] = 1;
  REP(i,m) {
    for (int j = sumb-b[i]; j >= 0; --j) {
      dp[j + b[i]] |= dp[j];
    }
  }

  int ans = -1;
  for (int j = sumb; j >= suma; --j) {
    if (dp[j]) ans = j - suma;
  }

  if (ans == -1) printf("Impossible");
  else printf("%d\n", ans);
}

Pełne rozwiązanie

W ogólnym przypadku musimy jeszcze zagwarantować, żeby każda potrawa była przygotowywana przez co najmniej $k$ kucharzy. Ponieważ kucharze mogą zmieniać potrawy o pełnych godzinach, więc w szczególności każda potrawa musi wymagać co najmniej $k$ godzin (więc jeśli mamy jakieś $a_i < k$, to od razu można przerwać program z odpowiedzią Impossible).

Dla każdego kucharza i każdej potrawy oznaczmy pierwszą godzinę, przez którą ten kucharz pracuje nad tą potrawą jako „specjalną”. Zatem musimy przydzielić dokładnie $nk$ godzin specjalnych. Widać też, że $i$-ty kucharz może obsłużyć co najwyżej $\min(b_i, n)$ godzin specjalnych.

Zatem dla podzbioru kucharzy $S$ możemy obliczyć $G_S = \sum_{i\in S} \min(b_i, n)$ jako maksymalną liczbę godzin specjalnych, które mogą być obsłużone przez podzbiór $S$. Więc w poprawnym rozwiązaniu musi być spełnione $G_S \geq nk$.

Okazuje się, że jest to warunek wystarczający (bo konstruując przypisanie potraw kucharzom z podzbioru wystarczy na początku przydzielić godziny specjalne, a potem resztę jakkolwiek).

Tak więc chcemy znaleźć taki podzbiór $S$, żeby $B_S$ było minimalne, $B_S \geq A$ oraz $G_S \geq nk$. Możemy w tym celu zmodyfikować nasze rozwiązanie problemu plecakowego, przez obliczanie $dp[j]$ jako maksymalna możliwa liczba godzin specjalnych $G_S$ dla pewnego podzbioru kucharzy $S \subseteq \{1,\ldots,i\}$, że $B_S = j$.

Poniższa modyfikacja również działa w złożoności czasowej $O(mB)$:

  REP(i,n) if (a[i] < k) {
    printf("Impossible\n");
    return 0;
  }
  
  REP(i,sumb+1) dp[i] = -infty;
  dp[0] = 0;

  REP(i,m) {
    for (int j = sumb-b[i]; j >= 0; --j) {
      dp[j + b[i]] = max(dp[j + b[i]], dp[j] + min(b[i], n));
    }
  }

  int ans = -1;
  for (int j = sumb; j >= suma; --j) {
    if (dp[j] >= n*k) ans = j - suma;
  }