E - Vitamin Balance Editorial by en_translator
This problem can be solved by, for each vitamin \(i\) \((1\leq i\leq 3)\), precalcaulting the maximum intake of vitamin \(i\) (ignoring the other vitamin) so that the total calorie consumption does not exceed \(j\) \((0\leq j\leq X)\), using dynamic programming (DP).
Initially, we compute the maximum intake of vitamin \(i\) (ignoring the other vitamin) so that the total calorie consumption is exactly \(j\).
Let \(dp_i[k][j]\) \((1\leq i\leq 3,~0\leq j\leq X,~0\leq k\leq N)\) represent the maximum intake of vitamin \(i\) when choosing foods from the \(1\)-st through \(k\)-th, so that the total calorie consumption is exactly \(j\) (or \(-\infty\) if it is impossible).
First, we have \(dp_i[0][0]=0\) and \(dp_i[0][j]=-1\) \((1\leq j\leq X)\).
Next, if food \(k\) \((1\leq k\leq N)\) does not contain vitamin \(i\), then \(dp_i[k][j]=dp_i[k-1][j]\). If it does, considering whether to eat or not, we have \(dp_i[k][j]=\max(dp_i[k-1][j],dp_i[k-1][j-C_k]+A_k)\) \((C_k\leq j)\). For \(j\leq c_k\), we have \(dp_i[k][j]=dp_i[k-1][j]\).
The sought value is the resulting \(dp_i[N][j]\).
Next, we consider \(M_{i,j}\), the maximum intake of vitamin \(i\) so that the total calorie consumption does not exceed \(j\) \((0\leq j\leq X\), which satisfies \(M_{i,j}=\displaystyle\max_{0\leq j'\leq j} dp_i[N][j']\). This can be computed incrementally as \(M_{i,0}=dp_i[N][0]\) and \(M_{i,j}=\max(M_{i,j-1},dp_i[N][j])\).
Finally, when the total calorie consumption of the food to intake vitamin \(i\) \((1\leq i\leq 3)\) is \(s_i\), the minimum intake among vitamin \(1\), \(2\), and \(3\) is given as \(\min(M_{1,s_1}, M_{2,s_2}, M_{3,s_3} )\), so the sought value is
\[ \max_{s_1+s_2+s_3=X} \min(M_{1,s_1}, M_{2,s_2}, M_{3,s_3} ). \]
The combination \((s_1,s_2,s_3)=(S_1,S_2,S_3)\) that maximizes \( \min(M_{1,s_1}, M_{2,s_2}, M_{3,s_3} )\)
can be found with a greedy algorithm.
Specifically, starting from \(S_1=S_2=S_3=0\), repeat the following operation \(X\) times:
Compare \(M_{1,S_1}\), \(M_{2,S_2}\), and \(M_{3,S_3}\).
If the smallest one is \(M_{i,S_i}\), increase \(S_i\) by \(1\).
If there are multiple smallest ones, you may choose any of them.
The final answer is the value \(\min(M_{1,S_1}, M_{2,S_2}, M_{3,S_3} )\) against the resulting \((S_1,S_2,S_3)\).
The time complexity is \(O(NX)\), which is fast enough.
Therefore, the problem has been solved.
Sample code in C++:
posted:
last update: