[HUSTFC 2023] 简单的加法乘法计算题 题解
hytallenxu
·
·
题解
题目简述
给定 2 种操作，询问使得 0 变到 y 的最小操作次数。
思路
首先考虑搜索或动态规划。
搜索就不多说了，开了个记忆化结果超时了。
考虑动态规划。
转移方程：
$dp_i=\min(f_i,f_{i/b_{j}}+1, dp_i)$，其中 $j \le m$，且 $i\bmod b_j =0$。
对于 $i \le y$，我们不难写出以下的核心代码：
```cpp
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)$，炸了。
当然，这道题肯定没有这么简单就直接使用裸的动规完成，于是考虑优化。
考虑复杂度瓶颈在第一标志处，可以使用[单调队列](https://www.luogu.com.cn/problem/P1886)解决，最终时间复杂度 $O(y \times (\log n+ m))$，可以通过此题。
## Code
```cpp
#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
```