1 条题解
-
1
m的范围很小，整体可以接受O(nm)的时间复杂度。可以考虑将状态定义为：f[i][j]表示考虑前i个烟花，且放第i个烟花时在位置j，得到的最大幸福值。设w = d * (t[i] - t[i - 1])，则f[i][j]可以由f[i-1][j-w]...f[i-1][j+w]转移得到，取其中的最大值即可。可以发现，固定i枚举j来求状态时，相当于求滑动窗口的最值，可以用单调队列来优化。 为了避免内存超限，需要采用滚动数组，即只保留当前行的状态，和上一行的状态，这样就可以把f数组第一维的长度降低到2，具体细节见代码。
参考代码
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int MAXN = 15e4 + 5; const int MAXM = 305; LL n, m, d, a[MAXM], b[MAXM], t[MAXM], f[2][MAXN], ans = -1e18; deque<int> q, q1; int main() { cin >> n >> m >> d; t[0] = 1; for (int i = 1; i <= m; i++) { cin >> a[i] >> b[i] >> t[i]; int cur = i & 1, pre = cur ^ 1; LL w = d * (t[i] - t[i - 1]); q = q1; for (int j = 1, r = 1; j <= n; j++) { while (!q.empty() && q.front() < j - w)//左端点 q.pop_front(); while (r <= j + w && r <= n) {//右端点 while (!q.empty() && f[pre][r] > f[pre][q.back()]) q.pop_back(); q.push_back(r); r++; } f[cur][j] = f[pre][q.front()] + b[i] - abs(a[i] - j); } } for (int i = 1; i <= n; i++) ans = max(ans, f[m & 1][i]); cout << ans; return 0; }
hetaowjl
LV 1
SU
@ 2024-5-23 10:41:56
- 1