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

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

Bessie is conducting a business trip in Bovinia, where there are?NN?(2≤N≤10002≤N≤1000) cities labeled?1…N1…N?connected by?MM?(1≤M≤20001≤M≤2000) one-way roads. Every time Bessie visits city?i,i,?Bessie earns?mimi?moonies (0≤mi≤10000≤mi≤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,?m1=0.m1=0.

Mooving between two cities via a road takes one day. Preparing for the trip is expensive; it costs?C?T2C?T2?moonies to travel for?TT?days (1≤C≤10001≤C≤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.

 

 

 

SAMPLE INPUT:

3 3 1
0 10 20
1 2
2 3
3 1

SAMPLE OUTPUT:

24

The optimal trip is?1→2→3→1→2→3→1.1→2→3→1→2→3→1.?Bessie makes?10+20+10+20?1?62=2410+20+10+20?1?62=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?tt?days then the amount of moonies that she makes is bounded above by?1000t?t2,1000t?t2,?which is negative when?t>1000.t>1000.?Thus, it suffices to keep track of the DP states?dp[x][t]dp[x][t]?for each?1≤x≤N,0≤t≤1000,1≤x≤N,0≤t≤1000,?denoting the maximum amount of moonies Bessie can make up to time?tt?if she is located at city?xx?at time?tt. The final answer will be?max0≤t≤1000(dp[1][t]?Ct2).max0≤t≤1000(dp[1][t]?Ct2).?This solution runs in?O(max(mi)?(N+M)).O(max(mi)?(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]

以上就是關(guān)于【USACO 2020 January Contest, Gold Problem 1. Time is Mooney】的解答，如需了解學校/賽事/課程動態(tài)，可至翰林教育官網(wǎng)獲取更多信息。

往期文章閱讀推薦：

AMC/BPhO/UKChO…下半年20+賽事集中開考！抓住競賽"黃金備賽期"！

2027 USAAIO人工智能奧賽報名進行中！Round 1新規(guī)出爐，2月開賽如何備考？