Skip to Content
CTRL K

Cloud Computing

Análisis oficial 

Puede tentarnos al principio hacer una DP bidimensional con la cantidad de compras de computadoras y la cantidad de pedidos de clientes, pero eso daría una transición fea e ineficiente.

En su lugar, agrupemos ambas cosas en un único arreglo de “transacciones”. Cada transacción tiene tres atributos: el cambio en la cantidad de núcleos, la frecuencia de reloj asociada de los núcleos y el cambio en las ganancias totales. Por ejemplo, el caso de ejemplo tendría un arreglo de transacciones que se ve así:

Cambio de núcleosFrecuencia de relojCambio de ganancia
42200-700
21800-10
202550-9999
42000-750
-11500300
-619001500
-324004550

Ahora ordenamos el arreglo por frecuencia de reloj en orden inverso, lo que da esto:

Cambio de núcleosFrecuencia de relojCambio de ganancia
202550-9999
-324004550
42200-700
42000-750
-619001500
21800-10
-11500300

Nótese que en este orden, mientras un pedido de cliente venga después de una compra de computadora, la computadora podrá satisfacer el pedido siempre que haya núcleos suficientes.

Esto simplifica drásticamente el problema. Ahora podemos definir \texttt{max\\_profits}[t][c] como la ganancia máxima que podemos obtener de las primeras tt transacciones dado que nos quedan cc núcleos. Con esto, el resto del problema es una mochila (knapsack) simple.

#include <algorithm>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
struct Transaction {
	int cores;
	int rate;
	int price;
};
 
int main() {
	vector<Transaction> poss_transactions;
	int max_computers = 0;
	int comp_num;
	std::cin >> comp_num;
	for (int c = 0; c < comp_num; c++) {
		Transaction trans;
		std::cin >> trans.cores >> trans.rate >> trans.price;
		trans.price = -trans.price;
		poss_transactions.push_back(trans);
		max_computers += trans.cores;
	}
	int order_num;
	std::cin >> order_num;
	for (int o = 0; o < order_num; o++) {
		Transaction trans;
		std::cin >> trans.cores >> trans.rate >> trans.price;
		trans.cores = -trans.cores;
		poss_transactions.push_back(trans);
	}
	/*
	 * if we sort like this, then the entire clock rate issue
	 * goes away as long as we process them in order
	 */
	std::sort(poss_transactions.begin(), poss_transactions.end(),
	          [](const Transaction &a, const Transaction &b) -> bool {
		          return a.rate != b.rate ? a.rate > b.rate : a.price < b.price;
	          });
 
	/*
	 * max_profits[t][c] = the maximum profit we can gain from the first
	 * t transactions given that we have c cores left
	 */
	vector<long long> max_profits(max_computers + 1, INT64_MIN);
	max_profits[0] = 0;
	for (const Transaction &t : poss_transactions) {
		vector<long long> new_max(max_profits);
		for (int c = 0; c <= max_computers; c++) {
			int prev_comp = c - t.cores;
			if (0 <= prev_comp && prev_comp <= max_computers &&
			    max_profits[prev_comp] != INT64_MIN) {
				new_max[c] = std::max(new_max[c], max_profits[prev_comp] + t.price);
			}
		}
		max_profits = new_max;
	}
	cout << *std::max_element(max_profits.begin(), max_profits.end()) << endl;
}
Fundamentos