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]