自动搬运

查看原文

来自洛谷，原作者为

	xiezheyuan 明明我已昼夜无间踏尽前路/梦想中的彼岸为何还未到/明明我已奋力无间/天天上路/我不死也为活更好/快要到终点才能知道/又再回到起点重头上路

搬运于2025-08-24 22:28:35，当前版本为作者最后更新于2022-03-05 14:42:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

免费的馅饼，免费的陷阱。

1.贪心做法

先对原数据排序（优先时间从小到大，然后是价值从大到小）。然后跑贪心。先选第一个，然后如果时间足够移动就移动。

时间复杂度是 $O(n\log n)$。

#include <bits/stdc++.h>
using namespace std;

struct Pie{
	int t,p,v;	
} a[100005],last;
int w,n,ans;

bool cmp(Pie x,Pie y){
	if(x.t==y.t){
		return x.v>y.v;
	}
	else{
		return x.t<y.t;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>w>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].t>>a[i].p>>a[i].v;
	}
	sort(a+1,a+n+1,cmp);
	last=a[1];
	ans=a[1].v;
	for(int i=2;i<=n;i++){
		if(2*(a[i].t-last.t)>=abs(a[i].p-last.p)){
			ans+=a[i].v;
			last=a[i];
		}
	}
	cout<<ans<<endl;
	return 0;
}

可以水 $50$ 分。

为什么不是满分，因为本题贪心没有最优解。

2.暴力DP

不难推出，如果设 $f[i]$ 为接住 第 $i$ 个节点，那么枚举 $j \in [1,i)$。

方程为:

当然，如果要接得到，需要满足 ：

最后的答案就是 ：

当然，边界条件为

时间复杂度是 $O(n^2)$。

代码如下：

#include <bits/stdc++.h>
using namespace std;

int f[100005];
int w,n,ans;

struct pie{
	int t,p,v;
	bool operator<(const pie nth) const {
		return t<nth.t;
	}
} pies[100005];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin>>w>>n;
	for(int i=1;i<=n;i++){
		cin>>pies[i].t>>pies[i].p>>pies[i].v;
	}
	sort(pies+1,pies+n+1);
	f[1]=pies[1].v;
	for(int i=1;i<=n;i++){
	    f[i]=pies[i].v;
		for(int j=1;j<i;j++){
			if(2*(pies[i].t-pies[j].t)>=abs(pies[i].p-pies[j].p)){
				f[i]=max(f[i],f[j]+pies[i].v);
			}
		}
	}
	for(int i=1;i<=n;i++){
		ans=max(f[i],ans);
	}
	cout<<ans<<endl;
	return 0;
}

可以水 $85$ 分。

（开O2 就 $90$ 分了）。

3.树状数组优化DP（正解）

可以考虑对DP方程的条件进行整理，可以得出:

$p[i]+2 \times t[i] \le p[j]+2 \times t[j] \text{ when }(p[i]-p[j]) \ge 0$。

$p[i]-2 \times t[i] \le p[j]+2 \times t[j] \text{ when }(p[i]-p[j]) \lt 0$。

然后只需要对 $p[i]-2\times t[i]$ 排序，按 $p[i]+2\times t[i]$ 离散化 为 $x[i]$ 。然后建一个维护最大值的树状数组，每次 $f[i]$ 的更新只需要是 $f[i]=\max_{i=1}^{x[i]}+a[i].v$ ，更新 $x[i]$ 为 $f[i]$ ，然后就统计答案。

时间复杂度为 $O(n\log n)$。

老师的做法，我也是半知半懂

代码如下：

#include <bits/stdc++.h>
using namespace std;

struct pies {
	int t, p, v, x;
} a[100010];

int tmp[100010], f[100010], n,w;
int tree[100010];


bool cmp(pies a, pies b) {
	return a.p - 2 * a.t >= b.p - 2 * b.t;
}

int lowbit(int x) {
	return x & -x;
}

void update(int x, int a) {
	for (int i = x ; i <= n ; i += lowbit(i)) {
		tree[i] = max(tree[i], a);
	}
}

int query(int x) {
	int ans = 0;
	for (int i = x ; i ; i = i - lowbit(i)) {
		ans = max(ans, tree[i]);
	}
	return ans;
}

int ans = 0;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>w>>n;
	for (int i = 1 ; i <= n ; i ++ ) {
		cin >> a[i].t >> a[i].p >> a[i].v;
		tmp[i] = a[i].p + 2 * a[i].t;
	}
	sort(tmp + 1, tmp + n + 1);
	for (int i = 1 ; i <= n ; i ++ ) {
		a[i].x = lower_bound(tmp + 1, tmp + n + 1, a[i].p + 2 * a[i].t) - tmp;
	}
	sort(a + 1, a + n + 1, cmp);
	for (int i = 1 ; i <= n ; i ++ ) {
		f[i] = query(a[i].x) + a[i].v;
		update(a[i].x, f[i]);
		ans = max(ans, f[i]);
	}
	cout << ans << endl;
	return 0;
}