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]