Home » 国际竞赛 » Details

USACO 2020 January Contest, Gold Problem 1. Time is Mooney

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月1日下午6:20

USACO 2020 January Contest, Gold Problem 1. Time is Mooney

Bessie is conducting a business trip in Bovinia, where there are? $N$ ?( $2 \leq N \leq 1000$ ) cities labeled? $1 \dots N$ ?connected by? $M$ ?( $1 \leq M \leq 2000$ ) one-way roads. Every time Bessie visits city? $i,$ ?Bessie earns? $m_{i}$ ?moonies ( $0 \leq m_{i} \leq 1000$ ). Starting at city 1 Bessie wants to visit cities to make as much mooney as she can, ending back at city 1. To avoid confusion,? $m_{1} = 0.$

Mooving between two cities via a road takes one day. Preparing for the trip is expensive; it costs? $C \cdot T^{2}$ ?moonies to travel for? $T$ ?days ( $1 \leq C \leq 1000$ ).

What is the maximum amount of moonies Bessie can make in one trip? Note that it may be optimal for Bessie to visit no cities aside from city 1, in which case the answer would be zero.

INPUT FORMAT (file time.in):

The first line contains three integers? $N$ ,? $M$ , and? $C$ .The second line contains the? $N$ ?integers? $m_{1}, m_{2}, \dots m_{N}$ .

The next? $M$ ?lines each contain two space-separated integers? $a$ ?and? $b$ ?( $a \neq b$ ) denoting a one-way road from city? $a$ ?to city? $b$ .

OUTPUT FORMAT (file time.out):

A single line with the answer.

SAMPLE INPUT:

SAMPLE OUTPUT:

The optimal trip is? $1 \to 2 \to 3 \to 1 \to 2 \to 3 \to 1.$ ?Bessie makes? $10 + 20 + 10 + 20 - 1 \cdot 6^{2} = 24$ ?moonies in total.

Problem credits: Richard Peng and Mark Gordon

<h3> USACO 2020 January Contest, Gold Problem 1. Time is Mooney 题解(翰林国际教育提供，仅供参考)</h3>
<p style="text-align: center;">题解请<a href="/register" target="_blank" rel="noopener">注册</a>或<a href="/login" target="_blank" rel="noopener">登录</a>查看</p>
[/hide]

(Analysis by Benjamin Qi)

If Bessie travels for exactly? $t$ ?days then the amount of moonies that she makes is bounded above by? $1000 t - t^{2},$ ?which is negative when? $t > 1000.$ ?Thus, it suffices to keep track of the DP states? $d p [x] [t]$ ?for each? $1 \leq x \leq N, 0 \leq t \leq 1000,$ ?denoting the maximum amount of moonies Bessie can make up to time? $t$ ?if she is located at city? $x$ ?at time? $t$ . The final answer will be? $max_{0 \leq t \leq 1000} (d p [1] [t] - C t^{2}) .$ ?This solution runs in? $O (max (m_{i}) \cdot (N + M)) .$ ?time.

Mark Chen's code:

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1005;
const int MAXT = 1005;
 
long long n, m, c;
long long value[MAXN];
long long dp[2][MAXN];
 
vector<pair<int, int>> edges;
 
int main() {
	freopen("time.in","r",stdin);
	freopen("time.out","w",stdout);
	cin >> n >> m >> c;
	for (int i = 1; i <= n; i++) {
		cin >> value[i];
	}
	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		edges.push_back(make_pair(a, b));
	}
	long long max_profit = 0;
	memset(dp, -1, sizeof dp);
	dp[0][1] = 0;
	for (int t = 1; t < MAXT; t++) {
		int p = t % 2;
		memset(dp[p], -1, sizeof dp[p]);
		for (auto& e : edges) {
			a = e.first;
			b = e.second;
			if (dp[1-p][a] >= 0) {
				dp[p][b] = max(dp[p][b], dp[1-p][a] + value[b]);
			}
		}
		max_profit = max(max_profit, dp[p][1] - c * t * t);
	}
	cout << max_profit << "\n";
}

[/hide]