题解 | #数位dp？#

题目已经告诉答案了，记忆化搜之[doge]

#include<bits/stdc++.h>
//#include<algorithm>

using namespace std;
using ll = long long;
using pis = pair<int,int>;
using mat = vector<vector<int>>;

const mask=(1<<20)-1;

inline int lowbit(int x){return x&(-x);}

int tim[1<<20],mp[1<<20],nowtim=0;

int dfs(int now){
    if(tim[now]==nowtim)return mp[now];
    if(now==0)return 0;
    int ans=min(lowbit(now)+dfs((now+lowbit(now))&mask),1+dfs((now<<1)&mask));
    tim[now]=nowtim;
    return mp[now]=ans;
}

void solve(){
    nowtim++;
    int n;
    cin>>n;
    cout<<dfs(n&mask)<<'\n';
    

}
signed main(){

    std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);
    int t=1;cin>>t;
    while(t--)
        solve();
        
}