今天每日写过了
所以再来一题
2998.
Minimun Number of Jiwp Buy a Reimu figure
to oin
题目:
给你x跟y
你可以对x做四种操作让他变成y
整除的话除以11
整除的话除以5
或是+1
或是-1
问你最小的操作次数是多少
思路:
用一般的dp
dp过去会发现之前的数字被改变了
所以是不行的
仔细想想
这x每次能变成的数字有限
让他用步数+1来bfs下次能走到的地方
这样就可以很有效率的用最小步数
找他能到的地方
```cpp
class Solution {
public:
int minimumOperationsToMakeEqual(int x, int y)
{
if(x<=y)return y-x;
vector<int> paper(10001,931104);
queue<pair<int,int>> go;
go.push({x,0});
paper[x] = 0;
while(!go.empty())
{
pair<int,int> n = go.front();
if(n.first==y)return n.second;
go.pop();
if(n.first+1 <= 10000 && paper[n.first+1] > n.second+1)
{
paper[n.first+1] = n.second+1 ;
go.push({n.first+1,n.second+1});
}
if(n.first-1 >= 0 && paper[n.first-1] > n.second+1)
{
paper[n.first-1] = n.second+1 ;
go.push({n.first-1,n.second+1});
}
if(n.first%11==0 && paper[n.first/11] > n.second+1)
{
paper[n.first/11] = n.second+1 ;
go.push({n.first/11,n.second+1});
}
if(n.first%5==0 && paper[n.first/5] > n.second+1)
{
paper[n.first/5] = n.second+1 ;
go.push({n.first/5,n.second+1});
}
}
return paper[y];
}
};
```