海南网站开发公司,网站生成移动版,常熟网站建设公司,郑州网站seo厂家文章目录题意思路传送门
题意
城镇中有nnn个位置#xff0c;有mmm个烟花要放#xff0c;第iii个烟花放出的时间记为tit_iti#xff0c;放出的位置记为aia_iai。如果烟花放出的时候你在位置xxx#xff0c;那么将收获bi−∣ai−x∣b_i-|a_i-x|bi−∣ai−x∣点的快乐…
文章目录题意思路传送门
题意
城镇中有nnn个位置有mmm个烟花要放第iii个烟花放出的时间记为tit_iti放出的位置记为aia_iai。如果烟花放出的时候你在位置xxx那么将收获bi−∣ai−x∣b_i-|a_i-x|bi−∣ai−x∣点的快乐值。
初始可以在任意位置每个单位时间可以移动不大于ddd个单位距离现在需要最大化你能获得的快乐值。
1≤n≤150000,1≤m≤300,1≤d≤n1\le n\le 150000,1\le m\le 300,1\le d\le n1≤n≤150000,1≤m≤300,1≤d≤n
1≤ai≤n,1≤bi≤1e9,1≤ti≤1e91\le a_i\le n,1\le b_i\le 1e9,1\le t_i\le 1e91≤ai≤n,1≤bi≤1e9,1≤ti≤1e9
保证ti≤ti1t_i\le t_{i1}ti≤ti1
思路
考虑暴力dpdpdp设f[i][j]f[i][j]f[i][j]代表第jjj次放烟花的时候在位置iii的最大快乐值转移方程如下f[i][j]max{f[k][j−1]bj−∣aj−i∣}f[i][j]max\{ f[k][j-1]b_j-|a_j-i| \}f[i][j]max{f[k][j−1]bj−∣aj−i∣}当然这里的kkk不是随便取的范围是j−d∗(ti−ti−1)≤k≤jd∗(ti−ti−1)j-d*(t_i-t_{i-1})\le k\le jd*(t_i-t_{i-1})j−d∗(ti−ti−1)≤k≤jd∗(ti−ti−1)转移方程中如果我们确定了i,ji,ji,j那么式子可以写成如下f[i][j]max{f[k][j−1]}bj−∣ai−i∣f[i][j]max\{f[k][j-1]\}b_j-|a_i-i|f[i][j]max{f[k][j−1]}bj−∣ai−i∣ 而前面一块就是区间最大值暴力一点就是建线段树让后logloglog查找但是显然1e91e91e9复杂度行不通所以考虑用单调队列O(1)O(1)O(1)查询最大值复杂度为O(nm)O(nm)O(nm)。
写完就过也太cao了
#includebits/stdc.h
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define Mid (tr[u].ltr[u].r1)
#define pb push_back
using namespace std;const int N1000010,INF0x3f3f3f3f,mod1e97;
typedef long long LL;int n,m,d;
LL f[2][N];
int q[N*10];void solve() {for(int i1;i2;i) {for(int j0;jN;j) {f[i][j]-1e18;}}scanf(%d%d%d,n,m,d);int pt0;int u0;for(int i1;im;i) {int a,b,t; scanf(%d%d%d,a,b,t);int ctt-pt;int hh0,tt-1;for(int j1,k1;jn;j) {LL lj-1ll*d*ct,rj1ll*d*ct;while(knkr) {while(hhttf[u][k]f[u][q[tt]]) tt--;q[tt]k;k;}while(hhttq[hh]l) {hh;}f[u^1][j]f[u][q[hh]]b-abs(a-j);}ptt; u^1;}LL ans-1e18;for(int i1;in;i) ansmax(ans,f[u][i]);CVprintf(%lld\n,ans);
}int main() {int _1;while(_--) {solve();}return 0;
}
