题解：P14078 [GESP202509 七级] 金币收集

A7F3jK9pR0xf_ · 2025-10-05 14:48:35 · 题解

一种无脑做法。

先给原序列排序，按 x 为第一关键字 t 为第二关键字从小到大排序。

然后考虑线性 dp，令 f_i 表示 [1,i] 进行完决策且第 i 个金币选了的最优金币数。有转移：

答案是 \max_{i=1}^n f_i，直接硬做是 O(n^2)，只能拿 70pts。

观察合法转移的判定条件：

移项：

这样有关 i 和 j 的量都移到了一边，这样我们可以先对 x_i-t_i 离散化，然后用一个支持单点取 \max / 区间查 \max 的线段树优化转移即可，时间复杂度 O(n\log n)，可以通过。

#include <bits/stdc++.h>
using namespace std;
#define il inline
typedef long long ll;
const int N = 1e5 + 10;
struct node
{
    int x, t;
    friend bool operator < (const node &n1, const node &n2)
    {
        return n1.x == n2.x ? n1.t < n2.t : n1.x < n2.x;
    }
}a[N];
int f[N], n, tot;
unordered_map<int, int> mp;
set<int> s;
struct node2
{
    int v;
}ST[N << 2];
il void push_up(int ind)
{
    ST[ind].v = max(ST[ind << 1].v, ST[ind << 1 | 1].v);
}
il void upd(int ind, int l, int r, int tl, int tr, int x)
{
    if(l == r)
    {
        ST[ind].v = max(ST[ind].v, x);
        return;
    }
    int mid = (l + r) >> 1;
    if(tl <= mid) upd(ind << 1, l, mid, tl, tr, x);
    if(tr > mid) upd(ind << 1 | 1, mid + 1, r, tl, tr, x);
    push_up(ind);
}
il int ask(int ind, int l, int r, int tl, int tr)
{
    if(tl > tr) return 0;
    if(tl <= l && r <= tr) return ST[ind].v;
    int mid = (l + r) >> 1;
    if(tl <= mid && tr > mid) return max(ask(ind << 1, l, mid, tl, tr), ask(ind << 1 | 1, mid + 1, r, tl, tr));
    if(tl <= mid) return ask(ind << 1, l, mid, tl, tr);
    return ask(ind << 1 | 1, mid + 1, r, tl, tr);
}
int main()
{
    cin >> n;
    for(int i = 1;i <= n;++i) 
    {
        cin >> a[i].x >> a[i].t;
        s.insert(a[i].x - a[i].t);
    }
    sort(a + 1, a + 1 + n);
    for(auto i : s) mp[i] = ++tot;
    int ans = 0;
    for(int i = 1;i <= n;++i)
    {
        if(a[i].x > a[i].t) continue;
        f[i] = ask(1, 1, tot, mp[a[i].x - a[i].t], tot) + 1;
        ans = max(ans, f[i]);
        upd(1, 1, tot, mp[a[i].x - a[i].t], mp[a[i].x - a[i].t], f[i]);
    }
    cout << ans;
    return 0;
}