526互联

luoguP7302 [NOI1998] 免费的馅饼

发布时间 2023-11-13 19:36:27作者: HL_ZZP

题目描述

SERKOI 最新推出了一种叫做“免费馅饼”的游戏：游戏在一个舞台上进行。舞台的宽度为 ww 格（从左到右依次用 11 到 ww 编号），游戏者占一格。开始时游戏者可以站在舞台的任意位置，手里拿着一个托盘。下图为天幕的高度为 44 格时某一个时刻游戏者接馅饼的情景。

游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或向右移动一格或两格，也可以站在原地不动。

当馅饼在某一时刻恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。当馅饼落在一个游戏者不在的格子里时该馅饼就消失。

写一个程序，帮助我们的游戏者收集馅饼，使得所收集馅饼的分数之和最大。

输入格式

第一行是用空格隔开的两个正整数，分别给出了舞台的宽度 ww 和馅饼的个数 nn。

接下来 nn 行，每一行给出了一块馅饼的信息。

由三个正整数组成，分别表示了每个馅饼落到舞台上的时刻 titi​，掉到舞台上的格子的编号 pipi​，以及分值 vivi​。

游戏开始时刻为 00。

输入文件中同一行相邻两项之间用一个空格隔开。

输入数据中可能存在两个馅饼的 titi​ 和 pipi​ 都一样。

输出格式

一个数，表示游戏者获得的最大总得分。

输入输出样例

输入 #1
3 4
1 2 3
5 2 3
6 3 4
1 1 5
输出 #1
12

说明/提示

对于 100%100% 的数据，1≤w≤1081≤w≤108，1≤n≤1051≤n≤105，1≤ti≤1081≤ti​≤108，1≤pi≤w1≤pi​≤w，1≤vi≤10001≤vi​≤1000。

 

dp很明显，但是如果是裸的dp
方程还是非常好搞的
f[i]=max{f[j]+v[i]},(t[j]-t[i])*2>=(abs(p[j]-p[i]))
还是很明显的
但是问题就是这个方程的复杂度是O(n^2)
这个题目可是n<10^5的啊
想了想，状态真的没什么可以优化的了，已经是极限了
考虑转移优化，观察转移的决策集合，发现这个min的范围有可能是可以优化的
如果可以通过区间查找来快速确定这个min的值，那就可以优化掉一个n
但是我们的决策集合在舞台上是没有一个能够帮助我们快速确定每一个状态的区间的，或者说是我们没法直接在舞台上用区间查找找到每一个状态转移需要的min
我们注意到j的范围其实是可以进行一些转化的
我们把和i和j有关的数值分别移动到不等号的两边，就得到了两边都之和i或者j有关的东西
这个东西不久可以用来维护区间查找了吗？
但是现在是O(nlogn)
这个区间查找可以直接用树状数组搞定，每次更新完了就在上面把对应的f[i]更新就好了
还有一个就是式子出来之后，因为绝对值的原因，会变成两个式子，分析一下就发现我们要的是两个条件都满足的式子
具体做法后面就没什么难度了，数据结构的基本应用吧

还好，唯一能够学习的地方就是对于数据结构的使用
其实在前面想的时候就有感觉这个决策集合是能够直接区间查询的
（主要是除了这个应该是没有其他可能的）
但是就是抓不住那个位置，现在应该能知道怎么搞了，对于这个比较简单的决策条件，其实就是直接从这上面入手就好了，把式子一化，什么都出来了
能学的就这个

现在看看，数据结构优化有两个点
一个是尝试从两个方向考虑，从前向后转移和从后向前转移，
另一个是对转移的的要求进行化简
这些操作的目的都是希望能够降低查找能够转移的状态时的复杂度
dp的复杂度不就是转移的时候的吗。。

这题的难度。。为什么我感觉也没有紫题。。。
奇怪

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
    char c=getchar();int a=0,b=1;
    for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
int w,n,f[100001],tr[100001],tmp[100001],ans;
struct pie
{
    int t,p,v,x;
}e[100001];
inline int lowbit(int x)
{
    return x&(-x);
}
bool cmp(pie a,pie b)
{
    return 2*a.t-a.p<=2*b.t-b.p;
}
inline void add(int i,int x)
{
    while(i<=n)
    {
        tr[i]=max(tr[i],x);
        i+=lowbit(i);
    }
}
inline int ask(int i)
{
    int ans=0;
    while(i>0)
    {
        ans=max(ans,tr[i]);
        i-=lowbit(i);
    }
    return ans;
}
map<int,int> m;
int tot;
int main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    w=read(),n=read();
    for(int i=1;i<=n;i++)
    {
        e[i].t=read();
        e[i].p=read();
        e[i].v=read();
        tmp[i]=2*e[i].t+e[i].p;
    }
    sort(tmp+1,tmp+1+n);
    for(int i=1;i<=n;i++)
        if(m[tmp[i]]==0)m[tmp[i]]=++tot;
    for(int i=1;i<=n;i++)
        e[i].x=m[2*e[i].t+e[i].p];
    sort(e+1,e+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        f[i]=ask(e[i].x)+e[i].v;
        add(e[i].x,f[i]);
        ans=max(ans,f[i]);
    }
    cout<<ans<<endl;
    return 0;
}

有一个点，就是我们要查询的式子是同时满足两个式子的
我是按照洛谷上面一个思路写的，非常的巧妙，理解也是非常优秀，很值得学习
就是我们要查询同时满足这两个式子的状态，普通的数据结构其实不是很好做，这个其实算是一个二位偏序了
按照顺序对的理解也可以，但是我感觉我这种理解抽象的更加的接近原理，也就是更深刻
其实用树状数组来维护就可以了。
我们可以用插入的顺序来维护一个条件，用树状数组本身带的一个顺序来维护另一个条件
就是，我们先按照一个条件来排序，按照这个顺序来进行dp，在把另一个顺序对应的值离散化掉，把dp的值按照这个离散化后的数值插入树状数组中
这样我们查询的时候，其实就是同时满足了两个条件
如果其中有一个条件不满足，那他要么已经被插入了树状数组，但是在我们查询的范围外，要么根本就还没有来得及插入树状数组中
这样我们就完成了一个二位偏序

（我是这么做到把一个逆序对查找讲的这么复杂的？）
但是逆序对查找其实就是二位偏序嘛
它需要满足的两个条件分别是

1.在数组中的位置在一个位置前
2.这个位置前比它小的数字

要满足的条件有且只有这两个，这不是非常明显的二位偏序吗？
（好东西啊，学到了，弄完dp就弄你，结束了但是没完全结束的数据结构）