【题解】免费的馅饼 BIT+DP bzoj2131 ——quhengyi11

题目

我是传送门酱 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);
}