P6005 [USACO20JAN] Time is Mooney G
题目描述
Bessie 正在安排前往牛尼亚的一次出差，那里有 \(N\)（\(2 \leq N \leq 1000\)）个编号为 \(1 \ldots N\) 的城市，由 \(M\)（\(1 \leq M \leq 2000\)）条单向的道路连接。Bessie 每次访问城市 \(i\) 都可以赚到 \(m_i\) 哞尼（\(0 \leq m_i \leq 1000\)）。从城市 \(1\) 出发，Bessie 想要赚到尽可能多的哞尼，最后回到城市 \(1\)。为了避免争议，\(m_1=0\)。
沿着两个城市之间的道路移动需要消耗一天。出差的准备工作十分费钱；旅行 \(T\) 天需要花费 \(C \times T^2\) 哞尼（\(1 \leq C \leq 1000\)）。
Bessie 在一次出差中最多可以赚到多少哞尼？注意有可能最优方案是 Bessie 不访问城市 \(1\) 之外的任何城市，在这种情况下结果应当为 \(0\)。
输入格式
输入的第一行包含三个整数 \(N\)、\(M\) 和 \(C\)。
第二行包含 \(N\) 个整数 \(m_1,m_2,\ldots, m_N\)。
以下 \(M\) 行每行包含两个空格分隔的整数 \(a\) 和 \(b\)（\(a \neq b\)），表示从城市 \(a\) 到城市 \(b\) 的一条单向道路。
输出格式
输出一行，包含所求的答案。
输入输出样例 #1
输入 #1
3 3 1
0 10 20
1 2
2 3
3 1
输出 #1
24
说明/提示
最优的旅行方案是 \(1 \to 2 \to 3 \to 1 \to 2 \to 3 \to1\)。Bessie 总共赚到了 \(10+20+10+20-1 \times 6^2=24\) 哞尼。
题解
考虑DP
设\(f_{i,j}\)为第\(i\)天到达城市\(j\)的最大收益
那么很显然，
转移方程为\(f_{i,j}=max(f{i-1,k})\)，其中\(k\)为与城市\(j\)相邻的城市
但\(i\)的范围并没有给出
那我们便可以手动推一下
因为收益不能为负
因此可得式子\(-c\times i^2 + max(m_i) \times i >= 0\)
我们令\(c\)取最小值\(1\)，\(max(m_i)\)取最大值\(1000\)
则\(-i^2+1000i?=0\)
则\(i(1000-i)>=0\)
可得\(i \le 1000\)
那么就可以愉快的AC这道题了
Code:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 7, inf = 0x3f3f3f3f;
struct edge{int to, pre;
}e[N << 1];
struct node{int u, w, t;bool operator<(const node &a)const{return w < a.w;}
};
int n, m, c;
int a[N];
int head[N], tot;
int f[N][N], ans;
void add(int x, int y){e[++tot] = {y, head[x]};head[x] = tot;
}
int main(){scanf("%d%d%d", &n, &m, &c);for(int i = 1; i <= n; i++){scanf("%d", a + i);} for(int i = 1; i <= m; i++){int x, y;scanf("%d%d", &x, &y);add(y, x);}memset(f, -1, sizeof(f));f[0][1] = 0;for(int i = 1; i <= 1000; i++){for(int j = 1; j <= n; j++){for(int k = head[j]; k; k = e[k].pre){int v = e[k].to;if(f[i - 1][v] != -1){f[i][j] = max(f[i][j], f[i - 1][v] + a[j]);}}}ans = max(ans, f[i][1] - c * i * i);}printf("%d\n", ans);return 0;
}