Bribing Friends

Análisis oficial (C++) 

Explicación

La dificultad de este problema viene del hecho de que podemos usar tanto moonies como cucuruchos de helado para sobornar amigos. Si solo tuviéramos un método de soborno, esto se convertiría en un simple problema de mochila 0/1.

Para simplificar, consideremos un gasto óptimo de cucuruchos de helado y moonies. Por cada cucurucho de helado que gastamos en una vaca $i$ dada, ahorramos $1$ moonie cada $X_i$ cucuruchos de helado. Intuitivamente, deberíamos distribuir los cucuruchos de helado entre los amigos con el $X_i$ más bajo, porque esto maximiza la cantidad de moonies que podemos ahorrar.

Esto se puede demostrar mediante un argumento de intercambio . Consideremos dos vacas $i$ y $j$, donde $X_i > X_j$. Si gastáramos cucuruchos de helado en la vaca $i$ en lugar de la vaca $j$, entonces cada moonie que ahorráramos necesitaría $X_i - X_j$ cucuruchos de helado más.

Para pasar esto a un problema de mochila 0/1, sea $dp[i]$ la popularidad máxima posible alcanzable en el estado $i$.

• Para $0 \leq i \leq B$, $i$ representa la cantidad de cucuruchos de helado usados, mientras que se usaron $0$ moonies.

• Para $B < i \leq B + A$, $i - B$ representa la cantidad de moonies usados después de usar todos los cucuruchos de helado utilizables.

Nuestra transición de estado depende de la cantidad de moonies y cucuruchos de helado que nos quedan.

• Si $i > B$, ya agotamos todos los cucuruchos de helado, y solo podemos usar moonies para sobornar amigos.

• Sea $R = B - i$ la cantidad restante de cucuruchos de helado en la posición $i$

  • Si $R$ alcanza para sobornar por completo al amigo actual, podemos elegir sobornar a ese amigo y usar $X_i \cdot C_i$ cucuruchos de helado en el proceso.

  • Si $R$ no alcanza para sobornar por completo al amigo actual, gastamos $C_i - \lfloor\frac{R}{X_i}\rfloor$ moonies para sobornar a ese amigo, empujando nuestro índice a $B + C_i - \lfloor\frac{R}{X_i}\rfloor$ ya que se consideran agotados todos los cucuruchos de helado.

Ordenamos los amigos por $X_i$ creciente. Esto garantiza que al recorrer a nuestros amigos, usamos nuestros helados primero en los amigos con menor $X_i$, antes de usar algún moonie. Al final, tomamos el máximo de nuestro arreglo de DP como respuesta.

Implementación

Complejidad temporal: $\mathcal{O}(N \cdot (A + B))$

#include <bits/stdc++.h>
using namespace std;
 
struct Friend {
	int popularity, cost, discount;
	Friend() : popularity(0), cost(0), discount(0) {}
};
 
bool x_sort(const Friend &f1, const Friend &f2) { return f1.discount < f2.discount; }
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n, moonies, ice_cream;
	cin >> n >> moonies >> ice_cream;
	vector<Friend> friends(n);
	for (int i = 0; i < n; i++) {
		cin >> friends[i].popularity >> friends[i].cost >> friends[i].discount;
	}
 
	sort(friends.begin(), friends.end(), x_sort);  // ordenamos por el mejor descuento
 
	vector<int> dp(moonies + ice_cream + 1, -1);  // -1 representa no visitado
	dp[0] = 0;
 
	for (const Friend &f : friends) {
		auto [popularity, cost, discount] = f;
		for (int i = moonies + ice_cream - cost; i >= 0; i--) {
			// saltamos si no está visitado
			if (dp[i] == -1) continue;
 
			// gastando solo moonies
			if (i >= ice_cream) {
				dp[i + cost] = max(dp[i + cost], dp[i] + popularity);
			}
 
			// gastando solo cucuruchos de helado
			else if (ice_cream - i >= cost * discount) {
				dp[i + cost * discount] =
				    max(dp[i + cost * discount], dp[i] + popularity);
			}
 
			// gastando una cantidad mixta de moonies y cucuruchos de helado
			else if (ice_cream + (cost - ((ice_cream - i) / discount)) <=
			         moonies + ice_cream) {
				int moonies_spent = cost - ((ice_cream - i) / discount);
				dp[ice_cream + moonies_spent] =
				    max(dp[ice_cream + moonies_spent], dp[i] + popularity);
			}
		}
	}
 
	cout << *max_element(dp.begin(), dp.end()) << '\n';
}