燃放烟火 / Watching Fireworks is Fun

题目链接：ybt高效进阶5-6-4 / luogu CF372C

题目大意

有一个长度为 n 的路，然后每个 1 个长度有一个点。
然后有 m 次烟火，都有放的时间和地点。
然后如果有一个烟火在 x 放了，你在 y，那这次的分数就是这个烟火本身的分数减去你和烟火的距离。
然后你初始的位置随意，你每个时间可以移动不超过 d 个距离。
然后要你最大化并输出你总共获得的分数和。

思路

（麻了一本通上写的读入是 $a,t,b$ 的读入的还是 $a,b,t$，非常差评）

首先普通的 DP。
设 $f_{i,j}$ 为 $i$ 个时刻，你在 $j$ 的最大分数。
然后发现时刻很多，但烟花很少，考虑离散化，并将同一个时刻的烟花统一处理。

接着两个时刻之间间隔的时间乘上 $d$ 就是 $dis$，你这次可以走的长度。（防止爆 int 我就直接和 $n$ 去 $\min$，反正无所谓）
然后 f i , j = min ⁡ ∣ j − k ∣ ⩽ d i s { f i − 1 , k } + g e t ( i , j ) f_{i,j}=\min\limits_{|j-k|\leqslant dis}\{f_{i-1,k}\}+get(i,j) fi,j​=∣j−k∣⩽dismin​{fi−1,k​}+get(i,j)。
（$get(i,j)$ 是第 $i$ 个时刻你在 $j$ 会获得的分数，可以直接很快的求出）

然后不难想到就是顺着倒着一个单调队列就可以优化掉，过掉。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

struct node {
	int a, t, b;
}a[150001];
int n, m, d, now, tot;
int sta[150001], l, r;
ll f[2][150001], ans;

bool cmp(node x, node y) {
	return x.t < y.t;
}

int abss(int x) {
	if (x < 0) return -x;
	return x;
}

int main() {
	scanf("%d %d %d", &n, &m, &d);
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d", &a[i].a, &a[i].b, &a[i].t);
	}
	
//	sort(a + 1, a + m + 1, cmp);
	
	memset(f, -0x7f, sizeof(f));
	for (int i = 1; i <= n; i++) f[0][i] = 0;
	a[0].t = 1;
	
	now = 1;
	for (int i = 1; now <= m; i++) {
		tot++;
		int st = now;
		now++;
		while (now <= m && a[now].t == a[now - 1].t) {
			now++;
		}
		int ed = now - 1;
		
		int dis = min(1ll * n, 1ll * d * (a[st].t - a[st - 1].t));
		l = 1; r = 0;//从前面过去
		for (int j = 1; j <= n; j++) {
			while (l <= r && j - sta[l] > dis) l++;
			if (l <= r) f[i & 1][j] = max(f[i & 1][j], f[(i + 1) & 1][sta[l]]);
			while (l <= r && f[(i + 1) & 1][sta[r]] <= f[(i + 1) & 1][j]) r--;
			sta[++r] = j;
		}
		l = 1; r = 0;//从后面过来
		for (int j = n; j >= 1; j--) {
			while (l <= r && sta[l] - j > dis) l++;
			if (l <= r) f[i & 1][j] = max(f[i & 1][j], f[(i + 1) & 1][sta[l]]);
			while (l <= r && f[(i + 1) & 1][sta[r]] <= f[(i + 1) & 1][j]) r--;
			sta[++r] = j;
		}
		
		for (int j = 1; j <= n; j++) {//计算每个位置在这个时刻的分数并加上
			f[i & 1][j] = max(f[i & 1][j], f[(i + 1) & 1][j]);
			ll newadd = 0;
			for (int k = st; k <= ed; k++) newadd += 1ll * (a[k].b - abss(a[k].a - j));
			f[i & 1][j] += newadd;
		}
		
		memset(f[(i + 1) & 1], -0x7f, sizeof(f[(i + 1) & 1]));
	}
	
	ans = -INF;
	for (int i = 1; i <= n; i++)
		ans = max(ans, f[tot & 1][i]);
	printf("%lld", ans);
	
	return 0;
}