今天每日寫過了
所以再來一題
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];
}
};
```