题解 | #数位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 湖南

相关推荐

自由水:这HR已经很好了,多的是已读不回和不读了
点赞 评论 收藏
分享
04-30 21:35
已编辑
长安大学 C++
晓沐咕咕咕:评论区没被女朋友好好对待过的计小将可真多。觉得可惜可以理解,毕竟一线大厂sp。但是骂楼主糊涂的大可不必,说什么会被社会毒打更是丢人。女朋友体制内生活有保障,读研女朋友还供着,都准备订婚了人家两情相悦,二线本地以后两口子日子美滋滋,哪轮到你一个一线城市房子都买不起的996清高计小将在这说人家傻😅
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务