题目

我是传送门酱QAQ

题解

这道题首先看到饼子是10w个的,显然地图大小并没有什么用,离散就行,因此我们可以猜想复杂度是一个log或者两个log的。

那按照套路就考虑二分啥的?

我们先试试吧,令$f[i]$表示收集第i个饼子时的最大收益,我们有
$$f[i]=max(f[j]) \quad(j \lt i \; \&\& \;|p[i]-p[j]|\leq 2(t[i]-t[j]))$$
显然因为每个饼子的pos不同,这是没有什么单调性可言的,二分啥呀?qhy这么菜只会n方qwq

接下来的事情就比较好玩了,我们考虑对转移条件进行化简,我们有
$$p[i]-p[j]\leq 2(t[i] – t[j]) \; \& \& \; p[j]-p[i]\leq 2(t[i]-t[j])$$
进一步化简
$$2t[j]-p[j]\leq 2t[i] – p[i] \; \& \& \; 2t[j]+p[j]\leq 2t[i]+p[i]$$
你会发现这不就是个二维偏序的情况吗,那我们随便搞搞就能用树状数组转移了。

令$x=2t[i]-p[j], y=2t[i]+p[i]$

我们对第一维排序,然后用树状数组维护转移即可,实现的时候就有个细节,要记得把第二维离散化一下树状数组才能放得下。

总结:有时候转移条件手玩一下可能会有意想不到的效果,不能将带log的复杂度局限于二分。

代码

#include<bits/stdc++.h> 
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 100005
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 998244353
#define up 10000
struct node{
    int x, y, v, id;
    friend bool operator < (node x, node y)
    {
        return x.x < y.x;
    }
}a[N];
int t, p, v, cnt, u[N], f[N], ans, n, m;
inline bool cmp (node x, node y) {return x.y < y.y;}
namespace BIT{
    int c[N];
    inline void add (int x, int val) {for (int i = x; i <= cnt; i += lowbit(i)) c[i] = std::max(c[i], val);}
    inline int query (int x) {int ret = 0; for (int i = x; i; i -= lowbit(i)) ret = std::max(c[i], ret); return ret;}
};
int main ()
{
    scanf("%d %d", &m, &n);
    fo (i, 1, n)
    {
        scanf("%d %d %d", &t, &p, &v);
        a[i].x = 2 * t - p;
        a[i].y = 2 * t + p;
        a[i].v = v;
        a[i].id = i;
    }
    std::sort(a + 1, a + n + 1, cmp);
    cnt = 1; u[1] = 1;
    fo (i, 2, n)
    {
        if (a[i].y != a[i - 1].y)
            ++cnt;
        u[i] = cnt;
    }
    fo (i, 1, n)
        a[i].y = u[i];
    std::sort(a + 1, a + n + 1);
    fo (i, 1, n)
    {
        f[i] = BIT::query(a[i].y) + a[i].v;
        BIT::add(a[i].y, f[i]);
        ans = std::max(ans, f[i]);
    }
    printf("%d", ans);
}
分类: 文章

quhengyi11

喵(ฅ>ω<*ฅ)

2 条评论

XZYQvQ · 2018年11月4日 11:15 下午

% QHY Dalao

emmmmm…

如果您发现LaTeX里打不出“{”和“}”

是因为正常情况下的LaTeX公式应该是:\{,表示是一个“{”字符

但是在K-XZY中,会先对文章进行Markdown上的解析,然后实时渲染LaTeX

这就导致了问题的发生——\{被Markdown解析为了一个字符“{”

然后LaTeX渲染就出问题了

因此在K-XZY中,如果你想在LaTeX公式里写“{”,你应当用\\{

这样Markdown会解析为\{,然后LaTeX渲染就正确啦!

另外我很想批判您的代码超过了80列

    quhengyi11 · 2018年11月5日 7:36 上午

    那啥,这两个花括号我会打呀,你是指max那里我用了小括号?好细心QAQ我只是可能习惯了打max函数所以写成小括号了(还有我喜欢BIT压行QAQ)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *