P3089 [USACO13NOV] Pogo-Cow S 弹簧踩高跷

P3089 [USACO13NOV] Pogo-Cow S 弹簧踩高跷

题目描述

In an ill-conceived attempt to enhance the mobility of his prize cow Bessie, Farmer John has attached a pogo stick to each of Bessie's legs. Bessie can now hop around quickly throughout the farm, but she has not yet learned how to slow down.

To help train Bessie to hop with greater control, Farmer John sets up a practice course for her along a straight one-dimensional path across his farm. At various distinct positions on the path, he places N targets on which Bessie should try to land (1 <= N <= 1000). Target i is located at position x(i), and is worth p(i) points if Bessie lands on it. Bessie starts at the location of any target of her choosing and is allowed to move in only one direction, hopping from target to target. Each hop must cover at least as much distance as the previous hop, and must land on a target.

Bessie receives credit for every target she touches (including the initial target on which she starts). Please compute the maximum number of points she can obtain.

FJ给奶牛贝西的脚安装上了弹簧，使它可以在农场里快速地跳跃，但是它还没有学会如何降低速度。

FJ觉得让贝西在一条直线的一维线路上进行练习，他在不同的目标点放置了N (1 <= N <= 1000)个目标点，目标点i在目标点x(i)，该点得分为p(i)。贝西开始时可以选择站在一个目标点上，只允许朝一个方向跳跃，从一目标点跳到另外一个目标点，每次跳跃的距离至少和上一次跳跃的距离相等，并且必须跳到一个目标点。

每跳到一个目标点，贝西可以拿到该点的得分，请计算他的最大可能得分。

输入格式

* Line 1: The integer N.

* Lines 2..1+N: Line i+1 contains x(i) and p(i), each an integer in the range 0..1,000,000.

输出格式

* Line 1: The maximum number of points Bessie can receive.

样例 #1

样例输入 #1

样例输出 #1

提示

There are 6 targets. The first is at position x=5 and is worth 6 points, and so on.

Bessie hops from position x=4 (8 points) to position x=5 (6 points) to position x=7 (6 points) to position x=10 (5 points).

题目大意

草场上有一条直线，直线上有若干个目标点。每个目标点都有一个分值和一个坐标。现在你可以选择其中任意一个目标点开始跳，只能沿一个方向跳，并且必须跳到另一个目标点。且每次跳的距离都不能少于上一次的距离。请问你能得到的最大分值是多少？、

方法一（线段树维护dp）

考试时就是想到了这个做法，但是改了时限100ms过不了

设 \(f_{i , j}\) 表示只通过 \(j\) 步到达点 \(i\) 的最大分值。

\(j\) 会炸空间？

\(j\) 其实最多只有 \(n^2\) 种可能，乱搞一下就好了

那么：

\[f_{i , j} = Max_{k = 1}^{i - 1}(Max_{l = 0}^jf_{k , l} + p_i) \]

用线段树维护一下 \(f_{k , l}\) 就好了

code

#include <bits/stdc++.h>
#define fu(x, y, z) for (int x = y; x <= z; x++)
#define fd(x, y, z) for (int x = y; x >= z; x--)
#define LL long long
using namespace std;
const int N = 1005, M = 1000005;
struct node {
    int x, p;
} t[N];
LL ans;
int n, cnt, flg[M], p[M], p1[M], K = 1000005, len, dis[N][N];
struct Tr {
    LL val;
    int lp, rp;
} tr[M * 8];
bool cmp(node x, node y) { return x.x < y.x; }
void glp(int x) { tr[x].lp = ++len; }
void grp(int x) { tr[x].rp = ++len; }
void updata(int x) { tr[x].val = max(tr[tr[x].lp].val, tr[tr[x].rp].val); }
void change(int x, int l, int r, int pos, LL v) {
    if (l == r)
        tr[x].val = max(tr[x].val, v);
    else {
        int mid = l + r >> 1;
        if (pos <= mid) {
            if (!tr[x].lp)
                glp(x);
            change(tr[x].lp, l, mid, pos, v);
        } else {
            if (!tr[x].rp)
                grp(x);
            change(tr[x].rp, mid + 1, r, pos, v);
        }
        updata(x);
    }
}
int query(int x, int l, int r, int pos) {
    if (r <= pos)
        return tr[x].val;
    else {
        int mid = l + r >> 1, max1 = 0, max2 = 0;
        if (tr[x].lp)
            max1 = query(tr[x].lp, l, mid, pos);
        if (mid < pos && tr[x].rp)
            max2 = query(tr[x].rp, mid + 1, r, pos);
        return max(max1, max2);
    }
}
void clear(int x) {
    if (tr[x].lp)
        clear(tr[x].lp);
    if (tr[x].rp)
        clear(tr[x].rp);
    tr[x].val = tr[x].lp = tr[x].rp = 0;
}
void fans() { fu(i, 1, n) ans = max(ans, tr[i].val); }
int main() {
    scanf("%d", &n);
    fu(i, 1, n) scanf("%d%d", &t[i].x, &t[i].p);
    sort(t + 1, t + n + 1, cmp);
    fu(i, 1, n) fu(j, 1, n) dis[i][j] = abs(t[i].x - t[j].x);
    fu(i, 1, n) fu(j, 1, n) {
        if (!flg[dis[i][j]]) {
            flg[dis[i][j]] = 1;
            p[++cnt] = dis[i][j];
            K = max(K, dis[i][j]);
        }
    }
    sort(p + 1, p + cnt + 1);
    fu(i, 1, cnt) p1[p[i]] = i;
    len = n;
    fu(i, 1, n) {
        ans = max(ans, 1ll * t[i].p);
        change(i, 0, K, p1[0], 1ll * t[i].p);
    }
    int k, k2;
    fu(i, 1, n) {
        fu(j, 1, i - 1) {
            k = query(j, 0, K, p1[dis[i][j]]);
            k2 = query(i, 0, K, p1[dis[i][j]]);
            if (k + t[i].p > k2)
                change(i, 0, K, p1[dis[i][j]], k + t[i].p);
        }
    }
    fans();
    fu(i, 1, n) clear(i);
    len = n;
    fu(i, 1, n) change(i, 0, K, p1[0], t[i].p);
    fd(i, n, 1) {
        fd(j, n, i + 1) {
            k = query(j, 0, K, p1[dis[i][j]]);
            k2 = query(i, 0, K, p1[dis[i][j]]);
            if (k + t[i].p > k2)
                change(i, 0, K, p1[dis[i][j]], k + t[i].p);
        }
    }
    fans();
    printf("%lld", ans);
}

然后因为查找函数没有加等号，就寄掉8分。

差点就AK了

方法二（单调队列维护dp）

设 \(f_{i , j}\) 表示从 \(j\) 到 \(i\) 的最大分值，用单调队列维护

~~好像宏定义会慢一点？~~

code

 #include <bits/stdc++.h>
#define LL long long
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
using namespace std;
const int N = 2005;
struct node {
    int x , p;
} t[N];
int n , k;
LL ans , f[N][N];
inline bool cmp (node x , node y) { return x.x < y.x; }
inline bool cmp1 (node x , node y) { return x . x > y.x; }
inline void fans (int flg) {
    memset (f , -0x3f , sizeof (f));
    if (flg == 1) sort (t + 1 , t + n + 1 , cmp);
    else sort (t + 1 , t + n + 1 , cmp1);
    for (int j = 1 ; j <= n ; j ++) {
        f[j][j] = t[j].p;
        for (int i = j + 1 , k = j + 1 ; i <= n ; i ++) {
            f[i][j] = f[i - 1][j] - t[i - 1].p;
            while (k > 1 && (t[j].x - t[k - 1].x) * flg <= (t[i].x - t[j].x )* flg)
                f[i][j] = max (f[i][j] , f[j][--k]);
            f[i][j] += t[i].p;
            ans = max (ans , f[i][j]);
        }
        ans = max (ans , f[j][j]);
    }
}
int main () {
    scanf ("%d" , &n);
    fu (i , 1 , n) scanf ("%d%d" , &t[i].x , &t[i].p);
    sort (t + 1 , t + n + 1 , cmp);
    fans (1);
    fans (-1);
    printf ("%lld" , ans);
    return 0;
}