今天每日寫過了 所以再來一題 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]; } }; ``` -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.129.159 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722915419.A.F46.html