P9020 [USACO23JAN] Mana Collection P 题解

首先考虑对于长为 \(d\le s\) 的最优路径，最优的方法一定是先在起点等 \(s-d\) 秒再走以确保收集到的最大。\(n\le 18\) 我们显然考虑状压 dp。考虑最大法力值难以计算，正难则反，考虑使未被选择的最小。于是我们设 \(dp_{sta,i}\) 表示状态为 \(sta\)，结尾为 \(i\) 的最小未被选择权值，那么对于 \(x\rightarrow y\)，\(dp_{sta|y,j}\leftarrow dp_{sta,i}+dis_{i,j}\times t_{sta}\)，\(t_{sta}\) 表示 \(sta\) 集合里的 \(m\) 之和。

考虑 \(O(1)\) 或 \(O(\log n)\) 地处理询问。显然 \(\operatorname{ans}=s\times t_{sta}-\min \{dp_{sta,i}\}\)。这是一个一次函数的形式，于是把 \(t\) 当作 \(k\)，\(dp\) 当作 \(b\)，\(s\) 当作 \(x\) 维护即可。注意值域很大，要动态开点。对于统计中存在的 \(d<s\) 的情形，显然贡献是某一个合法情况减去一些值，一定不优，于是不必考虑。

时间复杂度是 \(O(n^22^n+q\log V)\) 的。

代码：

#include <bits/stdc++.h>
#define N 19
#define int long long
using namespace std;
int n, nm;
int m[N];
int dp[(1 << N) + 2][N];
int dis[N][N];
int mon[(1 << N) + 2];
int cmn(int &x, int y) {
	x = min(x, y);
}
struct Node {
	int lc, rc;
	int k, b;
} e[10000002];
int tot, rt[N];
#define lc(i) e[i].lc
#define rc(i) e[i].rc
#define k(i) e[i].k
#define b(i) e[i].b
int sve(int x, int k, int b) {
	return k * x + b;
}
void update(int &p, int k, int b, int l, int r) {
	if (!p)
		p = ++tot;
	int mid = (l + r) >> 1;
	int lsm = sve(mid, k(p), b(p)), nwm = sve(mid, k, b);
	if (nwm > lsm)
		swap(k, k(p)), swap(b, b(p));
	if (l == r)
		return;
	if (sve(l, k, b) > sve(l, k(p), b(p)))
		update(lc(p), k, b, l, mid);
	if (sve(r, k, b) > sve(r, k(p), b(p)))
		update(rc(p), k, b, mid + 1, r);
}
int query(int p, int x, int l, int r) {
	if (!p)
		return 0;
	int ans = sve(x, k(p), b(p));
	if (l == r)
		return ans;
	int mid = (l + r) >> 1;
	if (x <= mid)
		return max(ans, query(lc(p), x, l, mid));
	return max(ans, query(rc(p), x, mid + 1, r));
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> nm;
	memset(dis, 0x3f, sizeof dis);
	for (int i = 0; i < n; i++)
		cin >> m[i], rt[i] = i + 1;
	tot = n;
	for (int i = 0; i < (1 << n); i++) 
		for (int j = 0; j < n; j++)
			if ((i >> j) & 1)
				mon[i] += m[j];
	for (int i = 1; i <= nm; i++) {
		int a, b, t;
		cin >> a >> b >> t;
		--a, --b;
		dis[a][b] = t;
	}
	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
	memset(dp, 0x7f, sizeof dp);
	for (int sta = 0; sta < (1 << n); sta++)
		for (int i = 0; i < n; i++)
			if ((sta >> i) & 1) {
				int stb = sta - (1 << i);
				if (stb == 0) {
					dp[sta][i] = 0;
					continue;
				}
				for (int j = 0; j < n; j++)
					if ((stb >> j) & 1)
						dp[sta][i] = min((__int128)dp[sta][i], dp[stb][j] + (__int128)mon[stb] * dis[j][i]);
			}
	for (int sta = 0; sta < (1 << n); sta++)
		for (int i = 0; i < n; i++) 
			if ((sta >> i) & 1)
				update(rt[i], mon[sta], -dp[sta][i], 1, 1e9);
	int q;
	cin >> q;
	while (q--) {
		int s, e;
		cin >> s >> e;
		cout << query(rt[e - 1], s, 1, 1e9) << "\n";
	}
	return 0;
}