题解 | #数位dp?#

数位dp?

https://ac.nowcoder.com/acm/contest/66877/A

题目已经告诉答案了,记忆化搜之[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();
        
}
全部评论
?嗷嗷,原来你用lowbit了。那没事了。嗯记忆化搜索过不去
点赞 回复 分享
发布于 2023-10-27 16:57 湖南

相关推荐

点赞 评论 收藏
分享
群星之怒:不是哥们,你就不好奇瘫痪三十年的老植物人是啥样的吗?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务