[ABC422F-G] 题解

[ABC422F-G] 题解

F - Eat and Ride

考虑 DP，DP 状态要么压和要么压长度，如果压和就很直接，但是显然复杂度会爆炸，如果压长度的话，可以发现每到一个新点都要算：这条路径中在它后面的点的个数乘上它的点权，所以考虑枚举路径总长度 \(d\)，那么设计状态 \(f_{i, j}\) 表示从 \(1\) 出发到达 \(i\) 经过 \(j\) 条边的最小代价，转移是 \(f_{i, j}\rightarrow f_{v, j + 1} + (d - j)a_v\)，可以发现把 \(d - j\) 换元后不用枚举长度了，转移变成了 \(f_{i, j}\rightarrow f_{v, j - 1} + ja_v\)，按照 \(j\) 从大到小的顺序转移即可。

时间复杂度：\(O(n^2)\)。

// Problem: F - Eat and Ride
// Contest: AtCoder - AtCoder Beginner Contest 422
// Author: Moyou#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define int long long
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef pair<PII, int> PIII;
typedef long long ll;
const int N = 5000 + 10;int n, m, a[N], dist[N][N];
vector<int> g[N];
bool st[N][N];
void dijkstra(int s) {priority_queue<PIII, vector<PIII>, greater<PIII> > heap;memset(dist, 0x3f, sizeof dist), memset(st, 0, sizeof st);for(int i = 0; i <= n; i ++) dist[1][i] = i * a[1];for(int d = n; d; d --) {for(int t = 1; t <= n; t ++) {for(auto v : g[t])if(dist[v][d - 1] > dist[t][d] + (d - 1) * a[v])dist[v][d - 1] = dist[t][d] + (d - 1) * a[v];}}
}signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; i ++) cin >> a[i];for(int i = 1, a, b; i <= m; i ++) cin >> a >> b, g[a].push_back(b), g[b].push_back(a);dijkstra(1);for(int i = 1; i <= n; i ++)cout << dist[i][0] << '\n';return 0;
}

G - Balls and Boxes

第一问直接做完全背包，第二问需要给每个盒子里面的球分配编号，但是同一个盒子里面没有顺序，所以这是一个多重集排列，也就是最后只需要给第一问的答案乘上系数：

\[\dfrac {n!}{a!b!c!} \]

\(a, b, c\) 分别代表有几个球放在 \(A, B, C\) 盒子里面。

提取 \(n!\)，考虑完全背包的转移式（假设转移 \(B\) 盒子）：

\[f_i = \sum_{j}f_{i - j}\dfrac 1{j!}[j\equiv 0\pmod {b}] \]

不难发现这个是卷积的形式，用 FFT/NTT 优化即可。
时间复杂度：\(O(n\log n)\)。

// Problem: F - Eat and Ride
// Contest: AtCoder - AtCoder Beginner Contest 422
// Author: Moyou#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define int long long
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef pair<PII, int> PIII;
typedef long long ll;
const int N = 5000 + 10;int n, m, a[N], dist[N][N];
vector<int> g[N];
bool st[N][N];
void dijkstra(int s) {priority_queue<PIII, vector<PIII>, greater<PIII> > heap;memset(dist, 0x3f, sizeof dist), memset(st, 0, sizeof st);for(int i = 0; i <= n; i ++) dist[1][i] = i * a[1];for(int d = n; d; d --) {for(int t = 1; t <= n; t ++) {for(auto v : g[t])if(dist[v][d - 1] > dist[t][d] + (d - 1) * a[v])dist[v][d - 1] = dist[t][d] + (d - 1) * a[v];}}
}signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; i ++) cin >> a[i];for(int i = 1, a, b; i <= m; i ++) cin >> a >> b, g[a].push_back(b), g[b].push_back(a);dijkstra(1);for(int i = 1; i <= n; i ++)cout << dist[i][0] << '\n';return 0;
}