[NOI1998] 免费的馅饼题解

题目大意

P7302 [NOI1998] 免费的馅饼

Solution

鲜花：

可爱数据结构优化带权 LIS。

今天是可爱 @zswangziye 的生日捏~

正解：

首先暴力 DP 可以轻易推出：

$$ f_i=\max\limits_{2(t_i-t_j)\geq |p_i-p_j|} f_j+v_i $$

但是这个是 $O(n^2)$，受不鸟一点。

灵机一动，这是个二维偏序啊，直接上树状数组维护。

首先把这个条件拆掉绝对值吧：

$$ \begin{align} 2t_i-p_i\geq 2t_j-p_j\\ 2t_i+p_i\geq 2t_j+p_j \end{align} $$

发现只要同时满足这两个式子，就满足了 $2(t_i-t_j)\geq |p_i-p_j|$。因为绝对值非负，所以一定满足 $t_i\geq t_j$。

那就可以以 $(1)$ 式排序，然后离散化 $(2)$ 的结果再用树状数组维护二维偏序。

这样就能同时满足两式。

劇終。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51


#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define ft first
#define sd second

const int N=2e5+5;

int n,m;
struct node
{
    int t,p,v,l,r;
}a[N];
int b[N],tr[N],f[N],tot;

void upd(int x,int k){
    for(;x<=tot;x+=x&-x)
        tr[x]=max(tr[x],k);
}

int qry(int x,int k=0){
    for(;x;x-=x&-x)
        k=max(k,tr[x]);
    return k;
}

signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++){
        int t,p,v;
        scanf("%lld%lld%lld",&t,&p,&v);
        a[i]={t,p,v,2*t-p,2*t+p};
        b[i]=2*t+p;
    }
    sort(b+1,b+m+1);
    tot=unique(b+1,b+m+1)-b-1;
    for(int i=1;i<=m;i++)
        a[i].r=lower_bound(b+1,b+tot+1,a[i].r)-b;
    sort(a+1,a+m+1,[](node x,node y){
        return x.l<y.l;
    });
    for(int i=1;i<=m;i++){
        int tmp=qry(a[i].r);
        upd(a[i].r,tmp+a[i].v);
    }
    printf("%lld\n",qry(tot));
    return 0;
}

[NOI1998] 免费的馅饼 题解

题目大意

Solution

代码

[NOI1998] 免费的馅饼题解