Air Cownditioning II

Explicación

Como se da $M = 10$ , podemos recorrer todos los $2^{10}$ subconjuntos posibles de aires acondicionados. Para cada uno, comprobamos si este subconjunto de aires acondicionados satisface los requisitos de las vacas recorriendo todas las posiciones posibles $i \in [1;100]$ . Para cada posición $i$ , podemos recorrer todos los aires acondicionados disponibles en el subconjunto actual para hallar la temperatura reducida en $i$ y recorrer todas las vacas para hallar la vaca en esta posición y su demanda. Si el requisito en cada posición se cumple, actualizamos el costo mínimo en consecuencia.

Podemos generar subconjuntos con recursión o con máscaras de bits: ambas formas se presentan a continuación.

Solución 1: Subconjunto con recursión

Complejidad temporal: $\mathcal{O}(2^M \cdot 100 \cdot (M + N))$

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int N, M;
// {s, t, c}
vector<array<int, 3>> cows;
// {a, b, p, m}
vector<array<int, 4>> air_conditioners;
// uses[i] == true: se usa el i-ésimo aire acondicionado
vector<bool> uses;
// la cantidad mínima de dinero necesaria para mantener cómodas a todas las vacas
int min_cost = numeric_limits<int>().max();
 
/**
 * A partir de 'uses', determinar si el subconjunto actual de aires acondicionados
 * cumple las restricciones y, si es así, actualizar el costo mínimo
 */
void update() {
	bool is_feasible = true;
 
	// recorrer todas las posiciones para comprobar si el subconjunto actual es factible
	for (int i = 1; i <= 100; i++) {
		// recorrer los aires acondicionados para hallar las unidades de enfriamiento actuales
		int cooling = 0;
		for (int j = 0; j < M; j++) {
			if (!uses[j]) { continue; }
			auto &[a, b, p, m] = air_conditioners[j];
			if (a <= i && i <= b) { cooling += p; }
		}
 
		// recorrer las vacas para hallar la vaca actual
		int cow_requirement = 0;
		for (int j = 0; j < N; j++) {
			auto &[s, t, c] = cows[j];
			if (s <= i && i <= t) {
				cow_requirement = c;
				break;
			}
		}
 
		// En cada posición, el requisito de la vaca debe cumplirse
		if (cooling < cow_requirement) {
			is_feasible = false;
			break;
		}
	}
 
	if (is_feasible) {
		int cost = 0;
		for (int i = 0; i < M; i++) {
			if (uses[i]) { cost += air_conditioners[i][3]; }
		}
		min_cost = min(min_cost, cost);
	}
}
 
/**
 * Expandir el subconjunto, representado por 'uses', eligiendo (no) usar el i-ésimo
 * aire acondicionado
 */
void search(int i) {
	if (i == M) {
		update();
	} else {
		uses[i] = false;
		search(i + 1);
		uses[i] = true;
		search(i + 1);
	}
}
 
int main() {
	cin >> N >> M;
 
	for (int i = 0; i < N; i++) {
		int s, t, c;
		cin >> s >> t >> c;
		cows.push_back({s, t, c});
	}
 
	for (int i = 0; i < M; i++) {
		int a, b, p, m;
		cin >> a >> b >> p >> m;
		air_conditioners.push_back({a, b, p, m});
	}
 
	uses.assign(M, false);
	search(0);
 
	cout << min_cost << endl;
}


import java.io.*;
import java.util.*;
 
public class AirConditioningII {
	static int N, M;
	// {s, t, c}
	static List<int[]> cows = new ArrayList<>();
	// {a, b, p, m}
	static List<int[]> airConditioners = new ArrayList<>();
	// uses[i] == true: se usa el i-ésimo aire acondicionado
	static boolean[] uses;
	// la cantidad mínima de dinero necesaria para mantener cómodas a todas las vacas
	static int minCost = Integer.MAX_VALUE;
 
	/**
	 * A partir de 'uses', determinar si el subconjunto actual de aires acondicionados
	 * cumple las restricciones y, si es así, actualizar el costo mínimo
	 */
	static void update() {
		boolean isFeasible = true;
 
		// recorrer todas las posiciones para comprobar si el subconjunto actual es factible
		for (int i = 1; i <= 100; i++) {
			// recorrer los aires acondicionados para hallar las unidades de enfriamiento actuales
			int cooling = 0;
			for (int j = 0; j < M; j++) {
				if (!uses[j]) continue;
				int[] ac = airConditioners.get(j);
				int a = ac[0], b = ac[1], p = ac[2];
				if (a <= i && i <= b) cooling += p;
			}
 
			// recorrer las vacas para hallar la vaca actual
			int cowRequirement = 0;
			for (int j = 0; j < N; j++) {
				int[] cow = cows.get(j);
				int s = cow[0], t = cow[1], c = cow[2];
				if (s <= i && i <= t) {
					cowRequirement = c;
					break;
				}
			}
 
			// En cada posición, el requisito de la vaca debe cumplirse
			if (cooling < cowRequirement) {
				isFeasible = false;
				break;
			}
		}
 
		if (isFeasible) {
			int cost = 0;
			for (int i = 0; i < M; i++) {
				if (uses[i]) cost += airConditioners.get(i)[3];
			}
			minCost = Math.min(minCost, cost);
		}
	}
 
	/**
	 * Expandir el subconjunto, representado por 'uses', eligiendo (no) usar el i-ésimo
	 * aire acondicionado
	 */
	static void search(int i) {
		if (i == M) {
			update();
		} else {
			uses[i] = false;
			search(i + 1);
			uses[i] = true;
			search(i + 1);
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
 
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int t = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			cows.add(new int[] {s, t, c});
		}
 
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int p = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			airConditioners.add(new int[] {a, b, p, m});
		}
 
		uses = new boolean[M];
		search(0);
 
		System.out.println(minCost);
	}
}


cows = []  # Lista para guardar {s, t, c} de cada vaca
air_conditioners = []  # Lista para guardar {a, b, p, m} de cada aire acondicionado
 
# la cantidad mínima de dinero necesaria para mantener cómodas a todas las vacas
min_cost = float("inf")
 
 
def update():
	"""
	A partir de 'uses', determinar si el subconjunto actual de aires acondicionados
	cumple las restricciones y, si es así, actualizar el costo mínimo
	"""
	global min_cost
	is_feasible = True
	# recorrer todas las posiciones para comprobar si el subconjunto actual es factible
	for i in range(1, 101):
		# recorrer los aires acondicionados para hallar las unidades de enfriamiento actuales
		cooling = 0
		for j in range(M):
			if not uses[j]:
				continue
			a, b, p, m = air_conditioners[j]
			if a <= i <= b:
				cooling += p
 
		# recorrer las vacas para hallar la vaca actual
		cow_requirement = 0
		for s, t, c in cows:
			if s <= i <= t:
				cow_requirement = c
				break
 
		# En cada posición, el requisito de la vaca debe cumplirse
		if cooling < cow_requirement:
			is_feasible = False
			break
 
	# Actualizar el costo mínimo si es factible
	if is_feasible:
		cost = sum(air_conditioners[i][3] for i in range(M) if uses[i])
		min_cost = min(min_cost, cost)
 
 
def search(i: int):
	"""Expandir el subconjunto, representado por 'uses', eligiendo (no) usar el i-ésimo aire acondicionado"""
	if i == M:
		update()
	else:
		uses[i] = False
		search(i + 1)
		uses[i] = True
		search(i + 1)
 
 
N, M = map(int, input().split())
uses = [False] * M  # uses[i] == true: se usa el i-ésimo aire acondicionado
for _ in range(N):
	s, t, c = map(int, input().split())
	cows.append((s, t, c))
 
for _ in range(M):
	a, b, p, m = map(int, input().split())
	air_conditioners.append((a, b, p, m))
 
search(0)
print(min_cost)

Solución 2: Subconjunto con máscara de bits

Complejidad temporal: $\mathcal{O}(2^M \cdot 100 \cdot (M + N))$

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
/** @return si las unidades de AC dadas cumplen las restricciones de las vacas */
bool check(vector<array<int, 3>> &cows, vector<array<int, 4>> &air_conditioners) {
	// recorrer todas las posiciones para comprobar si el subconjunto actual es factible
	for (int i = 1; i <= 100; i++) {
		// recorrer los aires acondicionados para hallar las unidades de enfriamiento actuales
		int cooling = 0;
		for (int j = 0; j < air_conditioners.size(); j++) {
			auto &[a, b, p, m] = air_conditioners[j];
			if (a <= i && i <= b) { cooling += p; }
		}
 
		// recorrer las vacas para hallar la vaca actual
		int cow_requirement = 0;
		for (int j = 0; j < cows.size(); j++) {
			auto &[s, t, c] = cows[j];
			if (s <= i && i <= t) {
				cow_requirement = c;
				break;
			}
		}
 
		// En cada posición, el requisito de la vaca debe cumplirse
		if (cooling < cow_requirement) { return false; }
	}
	return true;
}
 
int main() {
	int N, M;
	cin >> N >> M;
 
	vector<array<int, 3>> cows;
	for (int i = 0; i < N; i++) {
		int s, t, c;
		cin >> s >> t >> c;
		cows.push_back({s, t, c});
	}
 
	vector<array<int, 4>> air_conditioners;
	for (int i = 0; i < M; i++) {
		int a, b, p, m;
		cin >> a >> b >> p >> m;
		air_conditioners.push_back({a, b, p, m});
	}
 
	int min_cost = numeric_limits<int>().max();
	// usar una máscara de bits para obtener todos los subconjuntos
	for (int mask = 0; mask < (1 << M); mask++) {
		int cost = 0;
		vector<array<int, 4>> used_conditioners;
		for (int i = 0; i < M; i++) {
			if (mask & (1 << i)) {
				used_conditioners.push_back(air_conditioners[i]);
				cost += air_conditioners[i][3];
			}
		}
 
		if (check(cows, used_conditioners)) { min_cost = min(min_cost, cost); }
	}
 
	cout << min_cost << endl;
}


import java.io.*;
import java.util.*;
 
public class AirCownditioning {
	// BeginCodeSnip{Cow and AC Class}
	static class Cow {
		public int start, end;
		public int coolReq;
		public Cow(int start, int end, int coolReq) {
			this.start = start;
			this.end = end;
			this.coolReq = coolReq;
		}
	}
	static class AC {
		public int start, end;
		public int coolAmt;
		public int cost;
		public AC(int start, int end, int coolReq, int cost) {
			this.start = start;
			this.end = end;
			this.coolAmt = coolReq;
			this.cost = cost;
		}
	}
	// EndCodeSnip
 
	static final int MAX_STALL = 100;
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int cowNum = Integer.parseInt(initial.nextToken());
		int acNum = Integer.parseInt(initial.nextToken());
 
		Cow[] cows = new Cow[cowNum];
		for (int c = 0; c < cowNum; c++) {
			StringTokenizer cow = new StringTokenizer(read.readLine());
			cows[c] = new Cow(Integer.parseInt(cow.nextToken()),
			                  Integer.parseInt(cow.nextToken()),
			                  Integer.parseInt(cow.nextToken()));
		}
 
		AC[] acs = new AC[acNum];
		for (int a = 0; a < acNum; a++) {
			StringTokenizer ac = new StringTokenizer(read.readLine());
			acs[a] = new AC(
			    Integer.parseInt(ac.nextToken()), Integer.parseInt(ac.nextToken()),
			    Integer.parseInt(ac.nextToken()), Integer.parseInt(ac.nextToken()));
		}
 
		int minCost = Integer.MAX_VALUE;
		for (int mask = 0; mask < (1 << acNum); mask++) {
			// indexación desde uno
			int[] stalls = new int[MAX_STALL + 1];
 
			int cost = 0;
			for (int a = 0; a < acNum; a++) {
				if ((mask & (1 << a)) != 0) {
					for (int i = acs[a].start; i <= acs[a].end; i++) {
						stalls[i] += acs[a].coolAmt;
					}
					cost += acs[a].cost;
				}
			}
 
			boolean valid = true;
			for (Cow c : cows) {
				for (int i = c.start; i <= c.end; i++) {
					if (stalls[i] < c.coolReq) {
						valid = false;
						break;
					}
				}
			}
			if (valid) { minCost = Math.min(minCost, cost); }
		}
 
		System.out.println(minCost);
	}
}


from typing import NamedTuple
 
MAX_STALL = 100
 
 
class Cow(NamedTuple):
	start: int
	end: int
	cool_req: int
 
 
class AC(NamedTuple):
	start: int
	end: int
	cool_amt: int
	cost: int
 
 
cow_num, ac_num = [int(i) for i in input().split()]
cows = [Cow(*[int(i) for i in input().split()]) for _ in range(cow_num)]
acs = [AC(*[int(i) for i in input().split()]) for _ in range(ac_num)]
 
min_cost = float("inf")
for mask in range(1 << ac_num):
	stalls = [0 for _ in range(MAX_STALL + 1)]
 
	cost = 0
	for v, a in enumerate(acs):
		if mask & (1 << v):
			for i in range(a.start, a.end + 1):
				stalls[i] += a.cool_amt
			cost += a.cost
 
	valid = True
	for c in cows:
		for i in range(c.start, c.end + 1):
			if stalls[i] < c.cool_req:
				valid = False
				break
		if not valid:
			break
	else:
		min_cost = min(min_cost, cost)
 
print(min_cost)