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

一种无脑做法。

先给原序列排序，按

x

为第一关键字

t

为第二关键字从小到大排序。

然后考虑线性 dp，令

f_i

表示

[1,i]

进行完决策且第

i

个金币选了的最优金币数。有转移：

\begin{cases} x_i>t_i,f_i=0\\ x_i\leq t_i,f_i=\max_{j\in [1,i),x_i-x_j\leq t_i-t_j} f_j+1 \end{cases}

答案是

\max_{i=1}^n f_i

，直接硬做是

O(n^2)

，只能拿 70pts。

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

x_i-x_j\leq t_i-t_j

移项：

x_i-t_i\leq x_j-t_j

这样有关

i

和

j

的量都移到了一边，这样我们可以先对

x_i-t_i

离散化，然后用一个支持单点取

\max

/ 区间查

\max

的线段树优化转移即可，时间复杂度

O(n\log n)

，可以通过。

CPP

#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;
}

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

文章操作

相关推荐

评论

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