P9020 [USACO23JAN] Mana Collection P 题解

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;
}