CF372C Watching Fireworks is Fun 题解

Grussg · 2019-11-08 20:41:27 · 题解

Problem:CF372C~ Watching~ Fireworks~Is ~Fun

Description

一个城镇有n个区域,从左到右编号为1到n,每个区域之间距离1个单位距离。

节日中有m个烟花要放，给定放的地点a_i​,时间t_i​,以及一个参数b_i。如果你当时在区域x,那么你可以获得b_i - \vert a_i - x\vert的开心值。

你每个单位时间可以移动不超过d个单位距离。 你的初始位置是任意的(初始时刻为1),求你通过移动能获取到的最大的开心值。 数据范围：

Solution

先思考用什么算法。

如果是贪心，实际上是不好贪心的，因为它有多个参数。是蒟蒻的我也不会贪心

贪心不行，瞧上去又像是道乱搞题，那肯定是DP。

思考朴素DP

设f[i][j]为第i个烟❀的时候在第j个区间的最大开心值

推导方程

可见f[i][j]=min(f[i][j],f[i-1][k]+b_i - \vert a_i - x\vert) k\in[max(1,j-t\times d),min(n,j+t\times d)]~~t=t_i-t_{i-1}

朴素dp方程还是很好推的

但是看时间复杂度最大O(mn^2)是无法通过的

同时的数组f[300][150000]也是无法开下来的

先解决空间问题

优化1：

容易想到滚动数组第一维i显然不需要存那么多，只需要存下当前i和i-1即可，滚掉一维即可。

优化2：

同时求b_i - \vert a_i - x\vert的最大值，同时b_i是一个固定的参数， 我们可以转换成求- \vert a_i - x\vert的最大值，即\vert a_i - x\vert的最小值，这样可以更加方便操作

再想如何解决时间问题

优化3：

我们枚举i \to m是无法优化的，同时枚举每个位置j \to n也是无法避免的，所以说我们想如何优化k的遍历，因为我们只需要通过在k的范围内最小值来更新现在的f[i][j]。既然需要最小值，用单调队列优化即可。我们跑两遍，从1 \to n和从n \to 1跑一遍，分别从右和从左更新f[i][j]。还有问题的可以结合代码看看

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MaxN=152000;
ll n,m,d,sum;
ll a[MaxN],b[MaxN],t[MaxN],f[2][152000],q[MaxN];
template <class G> inline void read(G&x){
    bool f;char ch=getchar();
    for(f=false;!isdigit(ch);ch=getchar())if(ch=='-')f=true;
    for(x=0;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=getchar());
    x*=f==1?-1:1;
}
inline int abs(int x){
    if(x<0) return -x;
    return x;
}
signed main(){
    read(n),read(m),read(d);
    memset(f,0x3f3f3f,sizeof(f));
    for(register int i=1;i<=m;i++) read(a[i]),read(b[i]),read(t[i]),sum+=b[i];
    for(register int i=1;i<=n;i++) f[1][i]=abs(a[1]-i);
    for(register int i=2;i<=m;i++){
        int now=i&1,last=i&1^1,ti=t[i]-t[i-1];
        memset(f[now],0x3f3f3f,sizeof(f[now]));
        int head=1,tail=0;
        for(register int j=1;j<=n;j++){
            while (head<=tail&&q[head]<j-ti*d) ++head;
            while (head<=tail&&f[last][q[tail]]>f[last][j]) --tail;
            q[++tail]=j;
            f[now][j]=min(f[now][j],f[last][q[head]]+abs(a[i]-j));
        }
        head=1,tail=0;
        for(register int j=n;j>=1;j--){
            while (head<=tail&&q[head]>j+ti*d) ++head;
            while (head<=tail&&f[last][q[tail]]>f[last][j]) --tail;
            q[++tail]=j;
            f[now][j]=min(f[now][j],f[last][q[head]]+abs(a[i]-j));
        }       
    }
    ll ans=INT_MAX/2;
    for(register int i=1;i<=n;i++) ans=min(f[m&1][i],ans);
    cout<<sum-ans;
    return 0;
}

Postscript

这只是一道很naive的题

也感谢其他奆佬写的题解对我的帮助

更多的单调队列优化DP好题

1. [POI2014]PTA-Little Bird（板子）.

2. [NOI2011]Noi嘉年华

希望大家对单调队列优化的DP有更深的理解

C_{s_p}~_20^{1^9}~P_{l^us}~P^{l_{u_s}}

希望各位考完联赛能和最爱的人好好看一场烟花