C - 酱神赏花
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 262143/262143KB (Java/Others)
酱神去杭州赏花。
花展在一条街道上举行,这条街道上有一共有n个节点,自左而右从1到n编号,1号和n号是左右两个端点,两个相邻端点之间的距离为1.本次花展一共要展出m朵花,在第ti时刻,有一朵颜值为bi的花将在第ai个节点展出,如果酱神在ti时刻处于第x个节点,那么他能获得的开心值为bi−|x−ai|,注意这个值可能为负。
在t=1的时刻,酱神可以随意从1到n选出一个节点作为赏花的起点。在接下来的每个单位时间段中,酱神最多能移动d的距离。酱神每秒只能移动整数个距离,且任何时刻不能超出街道的范围。
他能获得的最大开心值为多少?
Input
第一行3个数n,m,d。
接下来m行,每行3个数ai,bi,ti。
1≤n≤105,1≤m≤100
1≤ai≤n
1≤bi≤109
1≤ti≤109
1≤d≤109
Output
输出一个数,酱神的最大开心值。
Sample input and output
Sample Input | Sample Output |
---|---|
30 4 2 |
-3 |
解题思路:
我们令f( i , j ) -> 目前第 j 朵花开,酱神正在坐标点 i 的最小花费.
我们考虑转移
F ( i , j ) = min ( F( u , j - 1) – abs( i – u ) ) + B[j]
不妨令 i > u
有
F( i ,j ) = min ( F( u , j – 1 ) ) + B[j] + u – i;
当i < u时同理
这样
我们维护一个单调队列即可,正反跑两遍即可.
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath> typedef long long ll;
using namespace std;
const int maxn = 1e5 + ;
ll f[maxn][];
int cur = , q[maxn];
ll n,m,d; typedef struct flower
{
ll a,b,t;
friend bool operator < (const flower & x,const flower & y)
{
return x.t < y.t;
}
}; flower A[+]; void init_f()
{
for(int i = ; i <= n ; ++ i)
f[i][cur] = -;
} int main(int argc,char *argv[])
{
scanf("%d%d%d",&n,&m,&d);
for(int i = ; i <= m ; ++ i)
scanf("%d%d%d",&A[i].a,&A[i].b,&A[i].t);
sort(A+,A++m);
for(int i = ; i <= n ; ++ i)
f[i][cur] = A[].b - abs(i - A[].a);
for(int j = ; j <= m ; ++ j)
{
ll limit = (A[j].t - A[j-].t)*d;
cur ^= ;
int front = , rear = ;
init_f();
for(int i = ; i <= n ; ++ i)
{
while(rear > front && f[i][cur^] >= f[q[rear-]][cur^])
rear--;
q[rear++] = i;
while(rear > front && (i - q[front]) > limit)
front++;
f[i][cur] = max(f[i][cur],f[q[front]][cur^] + A[j].b - abs(i - A[j].a));
}
front = , rear = ;
for(int i = n ; i >= ; -- i)
{
while(rear > front && f[i][cur^] >= f[q[rear-]][cur^])
rear--;
q[rear++] = i;
while(rear > front && (q[front] - i) > limit)
front++;
f[i][cur] = max(f[i][cur],f[q[front]][cur^] + A[j].b - abs(i - A[j].a));
}
}
ll ans = -;
for(int i = ; i <= n ; ++ i)
ans = max(ans,f[i][cur]);
printf("%lld\n",ans);
return ;
}
UESTC_酱神赏花 2015 UESTC Training for Dynamic Programming<Problem C>的更多相关文章
-
UESTC_酱神的旅行 2015 UESTC Training for Dynamic Programming<;Problem M>;
M - 酱神的旅行 Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) Submit ...
-
UESTC_男神的约会 2015 UESTC Training for Dynamic Programming<;Problem J>;
J - 男神的约会 Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) Submit ...
-
UESTC_男神的礼物 2015 UESTC Training for Dynamic Programming<;Problem A>;
A - 男神的礼物 Time Limit: 3000/3000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) Submit ...
-
UESTC_邱老师选妹子 2015 UESTC Training for Dynamic Programming<;Problem H>;
H - 邱老师选妹子 Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) Submi ...
-
UESTC_邱老师看电影 2015 UESTC Training for Dynamic Programming<;Problem F>;
F - 邱老师看电影 Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) Submi ...
-
UESTC_邱老师玩游戏 2015 UESTC Training for Dynamic Programming<;Problem G>;
G - 邱老师玩游戏 Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) Submi ...
-
UESTC_酱神寻宝 2015 UESTC Training for Dynamic Programming<;Problem O>;
O - 酱神寻宝 Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) Submit ...
-
UESTC_邱老师选妹子(二) 2015 UESTC Training for Dynamic Programming<;Problem I>;
I - 邱老师选妹子(二) Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) Su ...
-
UESTC_最少花费 2015 UESTC Training for Dynamic Programming<;Problem D>;
D - 最少花费 Time Limit: 30000/10000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) Submi ...
随机推荐
-
thinkphp利用行为扩展实现监听器
1.在User/login函数中添加如下代码 tag('login_listener',$result); //alert('success', '恭喜,登录成功', U('xx/yy')); 去掉跳 ...
-
OC2-重写
// // Dog.h // OC2-重写 // // Created by qianfeng on 15/6/17. // Copyright (c) 2015年 qianfeng. All rig ...
-
ANDROID SHAPE画圆形背景_ANDROID实现角标布局
ANDROID SHAPE画圆形背景_ANDROID实现角标布局 <?xml version="1.0" encoding="UTF-8"?> &l ...
-
数据传输对象(DTO)介绍及各类型实体比较
数据传输对象(DTO)介绍及各类型实体比较 本文将介绍DDD分层架构中广泛使用的数据传输对象Dto,并且与领域实体Entity,查询实体QueryObject,视图实体ViewModel等几种实体进行 ...
-
数字规律:Pascal‘s triangle
Given an integer n, return the number of trailing zeroes in n!. Note: Your solution should be in pol ...
-
【问题】VS问题集合,不用也要收藏防止以后使用找不到
在日常的使用或者工作当中我们的vs会时不时的给我一些小“惊喜”.让我们有时候无可奈何.这不今天我又遇到了所以我决定记录下这些,方便以后再次出现好解决. 无法启动iis express web 服务器 ...
-
微信公众号授权,支付,退款总结【shoucang】
1.支付前准备 1.1首先两个平台接入账户. 商户平台:https://pay.weixin.qq.com/index.php/core/home/login?return_url=%2F 公众平台: ...
-
nginx php-fpm conf文件编写
coco.conf ##upstream upstream php_coco_backend{ server 127.0.0.1:8019; } server { listen 80; server_ ...
-
[ZJOI2010]贪吃的老鼠(网络流+建图)
题目描述 奶酪店里最近出现了m只老鼠!它们的目标就是把生产出来的所有奶酪都吃掉.奶酪店中一天会生产n块奶酪,其中第i块的大小为pi,会在第ri秒被生产出来,并且必须在第di秒之前将它吃掉.第j只老鼠吃 ...
-
11--Python入门--面向对象
面向对象是Python的特点.面向对象主要通过类class的定义来实现.类class是用来描述具有相同属性和方法的对象的集合.类定义了该集合中的每个对象的共有属性和方法可以将类理解为一个模块,模块中包 ...