(cf372c) Watching Fireworks is Fun 发表于 2021-11-14 | 分类于 solution , dp 原题链接 思路:单调队列优化dp模板 设$d_{i,j}$为当放第$i$个烟花时在位置$j$的最大快乐值, 则有转移方程: max所取区间左右端点随j增加单调不降, 所以可以使用单调队列在$O(1)$的时间上取最大值. 代码:12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include <cstdio>#include <cctype>#include <climits>#include <deque>using namespace std;using LL = long long;const int Mn(150500), Mm(350);template<typename T> void qrd(T& x) { //快读 x = 0; int c = getchar(); while(!isdigit(c)) { c = getchar(); } while(isdigit(c)) { x = x*10 + c - '0'; c = getchar(); }}template<typename T, typename... Ts> void qrd(T& x, Ts&... xs) { qrd(x); qrd(xs...);}inline LL labs(LL x) { return x<0 ? -x : x;}struct Qd { //队列内元素 LL x, p; bool operator < (const Qd& rhs) const { return x<rhs.x; }};struct Grq { //单调队列封装 deque<Qd> q; Qd front() { return q.front(); } void pop() { q.pop_front(); } void push(Qd x) { while(!q.empty() && q.back()<x) { q.pop_back(); } q.push_back(x); } void clear() { q.clear(); }} gq;int a[Mm];LL b[Mm], t[Mm];LL f[2][Mn]; //dp数组, 滚动数组int main() { int n,m; LL d; qrd(n,m,d); for(int i(1);i<=m;++i) { qrd(a[i],b[i],t[i]); } t[0] = 1; for(int i(1);i<=m;++i) { gq.clear(); for(int j(1);j<=n && j<=(t[i]-t[i-1])*d;++j) { //初始化 gq.push({f[(i&1)^1][j],j}); } for(int j(1);j<=n;++j) { if(j+(t[i]-t[i-1])*d<=n) { //入队 gq.push({f[(i&1)^1][j+(t[i]-t[i-1])*d],j+(t[i]-t[i-1])*d}); } if(gq.front().p<j-(t[i]-t[i-1])*d) { //若队首元素不在可取区间则出队 gq.pop(); } f[i&1][j] = gq.front().x + b[i] - labs(a[i]-j); //可取区间最大值即为gq.front() } } LL ans(LONG_LONG_MIN); for(int i(1);i<=n;++i) { ans = f[m&1][i] > ans ? f[m&1][i] : ans; } printf("%lld\n",ans); return 0;}