CodeForces 372C :Watching Fireworks is Fun DP + 单调队列

zz/2024/5/21 21:26:59

传送门

题目描述

给出N个位子,排成一列,现在有M个烟花,每秒人的速度d,每个烟花有三个元素:a,b,t,表示在时刻t会绽放,如果我们在位子x观看到了的话,会获得b-abs(a-x)的欢乐值(可能为负而且所有烟花都必须观看);初始的时候可以在任何位子,问最高获得多少欢乐值。

分析

看完大概就知道需要DP搞一波
状态转移方程也比较好写
f[i][j] = max(f[i - 1][k] + b[i] - |a[i] - x|);

然后我们把b[i]提出来,可以转换成了求 |a[i] - x|的最小值。
k的范围应该是在x - dt * d ~ x + dt *d 之间,所以我们需要从1 - n跑一次,n - 1跑一次,每次记录一半区间内的最值

需要注意的是,[300][150000]的空间是明显开不下的,但是我们当前的状态仅需要上一维的状态进行状态转移,所以可以用类似于滚动数组的思想来优化空间

代码

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 152000;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll f[N];
ll back[N];
ll q[N];
ll a[N],b[N],t[N];
ll sum;
ll d;
int n,m;int main(){read(n),read(m),read(d);for(int i = 1;i <= m;i++){read(a[i]),read(b[i]),read(t[i]);sum += b[i];} for(int i = 1;i <= n;i++) f[i] = abs(i - a[1]);for(int i = 2;i <= m;i++){ll dt = t[i] - t[i - 1];memcpy(back,f,sizeof f);memset(f,0x3f,sizeof f);int hh = 1,tt = 0;for(int j = 1;j <= n;j++){while(hh <= tt && q[hh] < j - dt * d) hh++;while(hh <= tt && back[q[tt]] > back[j]) tt--;q[++tt] = j;f[j] = min(f[j],back[q[hh]] + abs(a[i] - j));}hh = 1,tt = 0;for(int j = n;j;j--){while(hh <= tt && q[hh] > j + dt * d) hh++;while(hh <= tt && back[q[tt]] > back[j]) tt--;q[++tt] = j;f[j] = min(f[j],back[q[hh]] + abs(a[i] - j));}}ll ans = 0x3f3f3f3f3f3f3f3f;for(int i = 1;i <= n;i++) ans = min(ans,f[i]);dl(sum - ans);return 0;
}/**
*  ┏┓   ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃       ┃
* ┃   ━   ┃ ++ + + +
*  ████━████+
*  ◥██◤ ◥██◤ +
* ┃   ┻   ┃
* ┃       ┃ + +
* ┗━┓   ┏━┛
*   ┃   ┃ + + + +Code is far away from  
*   ┃   ┃ + bug with the animal protecting
*   ┃    ┗━━━┓ 神兽保佑,代码无bug 
*   ┃        ┣┓
*    ┃        ┏┛
*     ┗┓┓┏━┳┓┏┛ + + + +
*    ┃┫┫ ┃┫┫
*    ┗┻┛ ┗┻┛+ + + +
*/

http://www.ngui.cc/zz/2727388.html

相关文章

CodeForces 961D:Pair Of Lines 思维

传送门 题目描述 在平面直角坐标系上给出n个点&#xff0c;求是否存在两条直线穿过所有点。 分析 前面三个点中&#xff0c;任意两个点必成一条直线&#xff0c;所以我们去枚举三个点中的两个&#xff0c;然后去判断其他的点是否在这条直线上&#xff0c;然后再判断不在这条…

CodeForces 319B :Psychos in a Line 单调栈

传送门 题目描述 有编号为1~N的N个人站成一排&#xff08;顺序是乱的&#xff09;&#xff0c;每人手中拿着一把枪。每一个时刻&#xff0c;每个人同时瞄准右边的人&#xff08;如果存在的话&#xff09;&#xff0c;然后如果这个人编号比自己大&#xff0c;则开枪将他打死。…

Wireless Password :ac自动机 + 状压DP

分析 f[i][j][k]表示第i位的情况下&#xff0c;在trie图上的位置位j的情况下匹配情况位k&#xff0c;状态转移方程就比较好写了 dp[i 1][tr[j][c]][l | cnt[tr[j][c]]] (dp[i 1][tr[j][c]][l | cnt[tr[j][c]]] dp[i][j][l]) % mod注意一下减去不合法的状态&#xff0c;节…

CodeForces 1367E :Necklace Assembly 思维

传送门 题目描述 给你一个字符串&#xff0c;你从中挑选一些让它们成为一个环&#xff0c;使得这个环朝一个方向转 k k k下&#xff0c;与原来看起来一样&#xff0c;找到你能够满足这个条件的可以挑选的最多的字符数量。 分析 我们去枚举 k k k的因子&#xff0c;那么我转…

POJ - 3635 :Full Tank? 最短路 + 拆点

分析 跟前段时间看的一个拆点求邻接矩阵快速幂的一个题有点像 这个题比较朴素的方法就是我把每个点剩余 j j j单位的汽油的最低花费处理出来&#xff0c;然后这样写毫无疑问会tle&#xff0c;所以我们需要去进行一些优化 首先我们思考一下这个朴素的思想为什么会超时&#xff…

CodeForces 546E :Soldier and Traveling 网络流 +拆点

传送门 题目描述 题意大概就是给定 n n n 个城市&#xff0c; m m m 条边。 然后人只能从走相邻边相连的城市。 现在给你初始城市的每一个人数&#xff0c;再给一组每个城市人数。询问是否可以从当前人数变换到给定人数。如果能&#xff0c;输入“YES”并输出方案&#xff0…

CodeForces 1312E : Array Shrinking 区间DP

传送门 题目描述 给你一个序列 a i a_{i} ai​&#xff0c;相邻两个数如果相同的话&#xff0c;我们可以删去其中一个数字&#xff0c;另一个数字1&#xff0c;最后留下来的序列最小可以是多少 分析 这个数据范围大概就能想到是区间DP问题了 我们首先初始化每一个区间f[i][…

CodeForces 1447D :Catching Cheaters 字符串DP

传送门 题目描述 给我们两个字符串&#xff0c;让我们从中选出两个字串&#xff0c;算出它们的最大公共子序列长度。然后将它乘4在减去两个字串的长度。问你这个数最大是多少。 分析 我们可以把这个式子转换为2 * LIS - a的剩余长度 - b的剩余长度&#xff0c;然后就可以设…

重建道路:树形DP

传送门 题目描述 分析 去年写的题&#xff0c;今天看猫猫博客的时候又想起来了这道题&#xff0c;回顾一些细节 f [ i ] [ j ] f[i][j] f[i][j]表示以 i i i为根节点保留 j j j个节点所要砍掉的道路数量&#xff0c;然后跑一下树形背包即可 代码 #include <bits/stdc.h…

CodeForces 715B :Complete The Graph最短路

传送门 题目描述 给n点m边&#xff0c;L&#xff0c;s&#xff0c;t 修改m条边中边为0的边&#xff0c; 使满足s,t的最短路长度是L&#xff0c;且输出答案的时候边为0的边的权值必须在[1,1e18]内 分析 感觉这道题细细思考能思考的东西有很多哇 首先我们去把所有可修改的边的…