自动搬运

查看原文

来自洛谷，原作者为

	Math_rad_round 旋转卡壳有2^4种读法，你知道吗？||NOIP退役苕皮

搬运于2025-08-24 22:05:32，当前版本为作者最后更新于2021-07-01 18:39:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

update: 修正代码错误

本题有两种不同做法，复杂度也不同。

这道题明显在某秒取第 $1$ 种还是第 $2$ 种收集对其他秒没有影响，所以如果在某一秒要收集，那直接取能量最高的一种收集就可以。

操作 $1$ 可以先把 $k,p$ 离线记录下来，用离散化或者 $map$ 计算到这一层某种类型的收集量。操作 $2$ 很好处理。这样我们就可以设 $y[i]$ 为第 $i$ 秒收集时获得的能量。

这样我们把题目简化到只需处理第 $3$ 种操作，对于第三种操作，有两种解法。

方案一：DP

很容易想到，设 $f[i][j]$为第 $i$ 秒用了 $j$ 加倍收集的最大能量值。转移方程就是。

前一个是正常收集，后一个是翻倍。

时间复杂度和空间复杂度都是 $O(nm)$ ，这道题里如果极限数据可以爆 $int$，开 $longlong$就快要用完空间了，那有什么其他方法吗？

方案二：转化+贪心

这道题的题解中，有一个人睿智的提出了一种贪心方法：

如果一次加倍都不用，答案明显是 $\sum_{i=1}^{n}y[i]$ 所有数的和。

而在 $a$ 位置用加倍相当于损失了 $y[a]$ 但增加了 $y[a+1]$。

所以我们可以设 $t[i]$ 为 $y[i+1]-y[i]$ ，也就是 $i$ 位置用翻倍的贡献，但因为不能连用翻倍魔法，问题转化为：

$n-1$ 个数 $t[i]$，最多取 $m$ 个不相邻的数，求所取数最大值。

很可惜的是这位同学的贪心方法错误，这道题现在类似于 P1484 正确方法是把这些数丢进优先队列，取出一个数时，将 两边的数-这个数 丢回队列。这样取出这个数等于放弃原来的数而取相邻的两个。详细解法见 P1484 的题解区 链接 。

时间复杂度 $O((n+m)log\ n)$。空间则只有 $O(n)$ 。

代码

DP:

#include<iostream>
#include<map>
using namespace std;

long long f[50002][501];
long long y[50002];
long long a1[50002];
long long a2[50002];
map<int,long long> u;
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a1[i]>>a2[i];
		y[i]=max(y[i-1],a2[i]);
	}	
	for(int i=1;i<=n;i++){
		int k;cin>>k;
		u[a1[i]]+=a2[i];
		y[i]=max(y[i],u[k]);
	}
	f[1][0]=y[1];
	for(int i=2;i<=n;i++){
		f[i][0]=f[i-1][0]+y[i];
		for(int j=1;j<=m;j++){
			f[i][j]=max(f[i-1][j]+y[i],f[i-2][j-1]+y[i]*2);
		}
	}
	long long ans=0;
	for(int i=0;i<=m;i++){
		ans=max(ans,f[n][i]);//不一定把m次用完
	}
	cout<<ans;
	return 0;
}

转化贪心：

#include<iostream>
#include<map>
#include<queue>
using namespace std;
struct dui{
	int s,t;
};
bool operator < (dui a,dui b){
	return a.s<b.s;
}
priority_queue<dui> d;
long long y[50002];
long long a1[50002];
long long a2[50002];
long long t[50002];
bool q[50002];
int fr[50002],be[50002],no[50002];
map<int,long long> u;
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a1[i]>>a2[i];
		y[i]=max(y[i-1],a2[i]);
	}	
	for(int i=1;i<=n;i++){
		int k;cin>>k;
		u[a1[i]]+=a2[i];
		y[i]=max(y[i],u[k]);
	}
	long long ans=y[1];
	for(int i=1;i<n;i++){
		ans+=y[i+1];//累加本来就有的
		t[i]=y[i+1]-y[i];
		fr[i]=i-1;be[i]=i+1;no[i]=t[i];
		d.push(dui{t[i],i});
	}
	no[0]=no[n]=0;be[n]=n;
	for(int i=0;i<m;i++){
		dui o=d.top();d.pop();int h=o.t;
		if(o.s<=0)break;//如果收益是负数自然就不需要用了
		if(q[h]==1){
			m++;continue;
		}
		q[fr[h]]=1;q[be[h]]=1;
		no[h]=no[fr[h]]+no[be[h]]-o.s;
		d.push(dui{no[h],h});
		fr[h]=fr[fr[h]];be[h]=be[be[h]];
		ans+=o.s;
	}
	cout<<ans;
	return 0;
}