自动搬运

查看原文

来自洛谷，原作者为

	hytallenxu 光之所指，影必随之，虽不能至，心向往之

搬运于2025-08-24 22:51:41，当前版本为作者最后更新于2023-10-22 20:59:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目简述

给定 $2$ 种操作，询问使得 $0$ 变到 $y$ 的最小操作次数。

思路

首先考虑搜索或动态规划。

搜索就不多说了，开了个记忆化结果超时了。

考虑动态规划。

转移方程：

$dp_i=\min(dp_{i-j}+1, dp_i)$，其中 $j \le n$。

$dp_i=\min(f_i,f_{i/b_{j}}+1, dp_i)$，其中 $j \le m$，且 $i\bmod b_j =0$。

对于 $i \le y$，我们不难写出以下的核心代码：

for(int j=2;j<=n;j++){
	f[i]=min(f[i],f[i-j]+1); //No.1
} 
			
for(int j=1;j<=m;j++){
	if(i%b[j]==0) f[i]=min(f[i],f[i/b[j]]+1); //No.2
}

时间复杂度 $O(n^2)$，炸了。

当然，这道题肯定没有这么简单就直接使用裸的动规完成，于是考虑优化。

考虑复杂度瓶颈在第一标志处，可以使用单调队列解决，最终时间复杂度 $O(y \times (\log n+ m))$，可以通过此题。

Code

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
int y,n,m;
int b[20];
int f[5000010];
map<int,int> pa;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int main(){
	y=read(),n=read(),m=read();
	for(int i=1;i<=m;i++) b[i]=read();
	if(n>=y){
		cout<<1<<endl;
		return 0;
	}
	for(int i=1;i<=y;i++){
		if(i<=n){
			f[i]=1;
			pa[1]++;
		}else if(i>=n+1){
			auto top=pa.begin();
			while(top->second==0) top++;
			int maxi=top->first;
			f[i]=maxi+1;
			pa[f[i-n]]--;
			if(pa[f[i-n]]==0){
				auto del=pa.find(f[i-n]);
				pa.erase(del);
			}
			
			
			for(int j=1;j<=m;j++){
				if(i%b[j]==0) f[i]=min(f[i],f[i/b[j]]+1);
			}
			pa[f[i]]++;
		}
	}
	cout<<f[y]<<endl;
	return 0;
}

最后

给出一组调试数据：

In:
2597207 753700 8
64 80 61 706 221 408 612 566 

Out:
3