Skip to Content
CTRL K

Time is Mooney

Análisis oficial (C++) 

Explicación

Definimos dp[t][i]\texttt{dp}[t][i] como el máximo de moonies que Bessie puede tener en la ciudad ii el día tt. Empezando con dp[0][0]=0\texttt{dp}[0][0] = 0, iteramos sobre cada día hasta TmaxT_{\text{max}}, el número máximo de días, y sobre cada ciudad, actualizando dp[t+1][j]\texttt{dp}[t + 1][j] para todas las ciudades jj alcanzables desde la ciudad ii mediante un camino dirigido.

Comparamos el valor actual de dp[t+1][j]\texttt{dp}[t + 1][j] con el valor de venir de una ciudad adyacente el día anterior, dp[t][i]+moonies[j]\texttt{dp}[t][i] + \text{moonies}[j], y tomamos el máximo. Después de procesar cada día, calculamos la ganancia como dp[t][0]−C⋅t2\texttt{dp}[t][0] - C \cdot t^2, que representa el total de moonies menos el costo de viaje de tt días, y llevamos registro de la ganancia máxima.

Nótese que la cantidad máxima de dinero que Bessie gana es 1000t−t21000t - t^2 en el caso en que gana 10001000 moonies por ciudad y el costo es 11 mooney. Esto también se debe a que los pesos de las aristas mim_i están acotados por 10001000 moonies. Sus ganancias se vuelven negativas cuando t>1000t > 1000, así que solo tenemos que revisar su movimiento entre las ciudades durante a lo sumo 10001000 días.

Implementación

Complejidad temporal: O(Tmax⋅(N+M))\mathcal{O}(T_{\text{max}} \cdot (N + M))

#include <bits/stdc++.h>
using namespace std;
 
const int MAX_DAYS = 1000;  // Maximum number of days Bessie can travel
 
int main() {
	ifstream read("time.in");
 
	int n, m, c;
	read >> n >> m >> c;
 
	vector<int> moonies(n);
	for (int i = 0; i < n; i++) { read >> moonies[i]; }
 
	vector<vector<int>> adj(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		read >> a >> b;
		a--, b--;  // Convert 1-indexed input to 0-indexed
		adj[a].push_back(b);
	}
 
	// dp[t][i]: max moonies at city i on day t
	vector<vector<int>> dp(MAX_DAYS, vector<int>(n, -1));
	// Base case: Start at city 0 (originally city 1) on day 0 with 0 moonies
	dp[0][0] = 0;
 
	int res = 0;
 
	for (int t = 0; t < MAX_DAYS; t++) {
		for (int i = 0; i < n; i++) {
			// Skip cities that are unreachable on day t
			if (dp[t][i] == -1) { continue; }
 
			// Transition: Consider all roads from city i to its neighbors
			for (int j : adj[i]) {
				if (t + 1 < MAX_DAYS) {
					// Update dp[t + 1][j] by considering a transition from an adjacent
					// city on the previous day
					dp[t + 1][j] = max(dp[t + 1][j], dp[t][i] + moonies[j]);
				}
			}
		}
 
		// Calculate profit if Bessie returns to city 0 (originally city 1) on day t
		res = max(res, dp[t][0] - c * t * t);
	}
 
	ofstream("time.out") << res << "\n";
}
import java.io.*;
import java.util.*;
 
public class Main {
	static final int MAX_DAYS = 1000;  // Maximum number of days Bessie can travel
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("time.in"));
		PrintWriter pw =
		    new PrintWriter(new BufferedWriter(new FileWriter("time.out")));
 
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
 
		int[] moonies = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) { moonies[i] = Integer.parseInt(st.nextToken()); }
 
		List<List<Integer>> adj = new ArrayList<>();
		for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); }
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			adj.get(a).add(b);
		}
 
		// dp[t][i]: max moonies at city i on day t
		int[][] dp = new int[MAX_DAYS][n];
		for (int[] row : dp) Arrays.fill(row, -1);
		// Base case: Start at city 0 (originally city 1) on day 0 with 0 moonies
		dp[0][0] = 0;
 
		int res = 0;
 
		for (int t = 0; t < MAX_DAYS; t++) {
			for (int i = 0; i < n; i++) {
				// Skip cities that are unreachable on day t
				if (dp[t][i] == -1) { continue; }
 
				// Transition: Consider all roads from city i to its neighbors
				for (int j : adj.get(i)) {
					if (t + 1 < MAX_DAYS) {
						// Update dp[t + 1][j] by considering a transition from an
						// adjacent city on the previous day
						dp[t + 1][j] = Math.max(dp[t + 1][j], dp[t][i] + moonies[j]);
					}
				}
			}
 
			// Calculate profit if Bessie returns to city 0 (originally city 1) on day t
			res = Math.max(res, dp[t][0] - c * t * t);
		}
 
		pw.println(res);
		pw.close();
	}
}
with open("time.in", "r") as fin:
	n, m, c = map(int, fin.readline().split())
	moonies = list(map(int, fin.readline().split()))
 
	adj = [[] for _ in range(n)]
	for _ in range(m):
		a, b = map(int, fin.readline().split())
		adj[a - 1].append(b - 1)  # Convert 1-indexed input to 0-indexed
 
MAX_DAYS = 1000  # Maximum number of days Bessie can travel
 
# dp[t][i]: max moonies at city i on day t
dp = [[-1] * n for _ in range(MAX_DAYS)]
# Base case: Start at city 0 (originally city 1) on day 0 with 0 moonies
dp[0][0] = 0
 
res = 0
 
for t in range(MAX_DAYS):
	for i in range(n):
		# Skip cities that are unreachable on day t
		if dp[t][i] == -1:
			continue
 
		# Transition: Consider all roads from city i to its neighbors
		for j in adj[i]:
			if t + 1 < MAX_DAYS:
				# Update dp[t + 1][j] by considering a transition from an adjacent city on the previous day
				dp[t + 1][j] = max(dp[t + 1][j], dp[t][i] + moonies[j])
 
	# Calculate profit if Bessie returns to city 0 (originally city 1) on day t
	res = max(res, dp[t][0] - c * t * t)
 
with open("time.out", "w") as fout:
	fout.write(f"{res}\n")
Fundamentos