21南京 J. Xingqiu's Joke 题解(思维+dp)

题目链接

题目思路

比赛的时候差不多想到了

其实就是他们的差值要么不变，要么除以因子，能除肯定要尽可能除

而有很多多余的状态没有必要表示，只要记录哪些dif改变的情况即可其实没那么难，就是要去掉很多表示状态即

代码

#include
#define fi first
#define se second
#define pii pair
#define debug cout<<"I AM HERE"< dp;
vector vec;
int dfs(int b,int dif){
    if(b==1) return 0;
    if(dp.count({b,dif})) return dp[{b,dif}];
    int ans=b-1;
    for(auto x:vec){
        if(dif%x==0){
            if(b>=x){
                ans=min(ans,dfs(b/x,dif/x)+b%x+1);
            }
            ans=min(ans,dfs(b/x+1,dif/x)+x-b%x+1);
        }
    }
    return dp[{b,dif}]=ans;
}
signed main(){
    int _;scanf("%d",&_);
    while(_--){
        vec.clear();
        dp.clear();
        scanf("%d%d",&a,&b);
        if(a