Problem - 372C - Codeforces
题目大意：
城镇中有n个位置，有 m个烟花要放。第i个烟花放出的时间记为 t，放出的位置记为a 。如果烟花放出的时候，你处在位置x，那么你将收获b-abs(a-x)点快乐值。
初始你可在任意位置，你每个单位时间可以移动不大于d 个单位距离。现在你需要最大化你能获得的快乐值。
(1?≤?n?≤?150000; 1?≤?m?≤?300; 1?≤?d?≤?n).
题解：
怎么dp呢......设一维时间，一维位置，差不多了。但是位置有点大，如果i为时间，j为位置，从k来， 空间300*150000开不出来。
怎么办呢.......好像可以滚动欸，那就是2*150000了，空间解决，那么两个位置150000*150000两个for循环肯定寄。怎么优化呢......
发现枚举i，j后，k好像可以一直维护在决策范围内，最优的话可以用单调队列维护，那么时间也解决了。
/*keep on going and never give up*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
inline int read()
{int x=0,k=1; char c=getchar();while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();return x*k;
}
const double E = exp(1);
const double PI = acos(-1.0);
const int mod=1e9+7;
const int maxn = 150000 + 10;
const int maxm = 300 + 10;
ll dp[2][maxn];
ll a[maxm], b[maxm], t[maxm];
int n, m, d;
int que[maxn];
int fl = 1;
void init() {memset(dp, 0x3f, sizeof(dp));memset(que, 0, sizeof(que));for(int i=1;i<=n;i++)dp[0][i]=0;fl=1;
}
void solve() {init();for (int i=1;i<=m;i++) {int l=1,r=0,k=1;for (int j=1;j<=n;j++) { for (;k<=min(1ll*n,j+d*(t[i]-t[i-1]));k++) {while (l<=r&&dp[fl^1][que[r]]<=dp[fl^1][k]) r--;que[++r]=k;}while(l<=r&&que[l]<max(1ll,j-d*(t[i]-t[i-1]))) l++;dp[fl][j] = dp[fl^1][que[l]]-abs(a[i]-j)+b[i];}fl^=1;}
}
signed main() {cin>>n>>m>>d;for (int i=1;i<=m;i++) cin>>a[i]>>b[i]>>t[i];solve();ll ans=-1e18;for(int i=1;i<=n;i++) ans=max(ans,dp[fl^1][i]);cout<<ans<<endl;return 0;}ps：没想到单调队列还不会，只会单调栈，这里还是用数组模拟的，用duque也可以，学一手也好。