C - 酱神赏花
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 262143/262143KB (Java/Others)
Submit Status
酱神去杭州赏花。
花展在一条街道上举行，这条街道上有一共有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
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 ;
}