关注
100%代码:
#include<bits/stdc++.h>
using namespace std;
const int N=16384;
unordered_map<int,int> dp[N];
int mi[N];
void solve(){
memset(mi,0x3f,sizeof mi);
dp[1][1]=2;
mi[1]=1;
for(int i=2;i<N;i++){
int minx=1e9;
for(int j=1;j<=i/j;j++){
if(i%j) continue;
int a=j;
dp[i][a]=mi[a]+i/a;
minx=min(minx,dp[i][a]);
a=i/j;
dp[i][a]=mi[a]+i/a;
minx=min(minx,dp[i][a]);
}
dp[i][i]=minx+2;
dp[i][1]=min(dp[i][1],minx+2);
for(auto [a,b]:dp[i]){
mi[a]=min(mi[a],b-i/a);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
int t=1;
cin>>t;
while(t--){
int num;
cin>>num;
int res=1e9;
for(auto [a,b]:dp[num]){
//cout<<num<<" "<<a<<" "<<b<<endl;
res=min(res,b);
}
cout<<res<<endl;
}
return 0;
}
想了好几个错解,一小时才过,我这方法感觉有点垃圾,但是能过。
查看原帖
2 1
相关推荐
05-16 11:04
广东财经大学 计算机类 点赞 评论 收藏
转发
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
821644次浏览 13034人参与
# 机械制造薪资爆料 #
319981次浏览 3732人参与
# 晒一晒我的offer #
3466698次浏览 55258人参与
# 0offer是寒冬太冷还是我太菜 #
427922次浏览 4944人参与
# 你觉得找工作该拿大厂还是小厂练手 #
61601次浏览 872人参与
# 荣耀求职进展汇总 #
70607次浏览 717人参与
# 如果可以选,你最想从事什么工作 #
186034次浏览 3077人参与
# 实习生应该准时下班吗 #
80735次浏览 592人参与
# 金三银四,你有感觉到吗 #
329131次浏览 4221人参与
# 海康威视求职进展汇总 #
101587次浏览 1217人参与
# 正在春招的你,也参与了去年秋招吗? #
136445次浏览 1705人参与
# 实习必须要去大厂吗? #
13834次浏览 219人参与
# 实习工作,你找得还顺利吗? #
42405次浏览 469人参与
# 我在牛爱网找对象 #
49790次浏览 322人参与
# 软件开发投递记录 #
479107次浏览 7242人参与
# 宁德时代求职进展汇总 #
37044次浏览 413人参与
# 国企vs私企,你更想去? #
20268次浏览 205人参与
# 求职遇到的搞笑事件 #
19673次浏览 287人参与
# 想实习转正,又想准备秋招,我该怎么办 #
117817次浏览 1328人参与
# 正在实习的你,有转正机会吗? #
106414次浏览 1043人参与