题解 P2618 【数字工程】

asuldb · 2018-07-19 20:05:07 · 题解

记忆化搜索，轻松最优解第三

这道题把思路写到题目下面也是没谁了

那就照着题目下面给你的思路写就行了

我们用dp[i]表示从i到1的最小花费

一遍欧拉筛之后直接上记搜

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<bitset>
#define re register
#define maxn 1000001
#define INF 999999999
using namespace std;
bitset<maxn> f;
int p[maxn],dp[maxn];
int T,n[maxn],tot;
void solve(int x)
{
    if(dp[x]!=INF) return;//已经找到，那么就不用搜了
    solve(x-1);
    dp[x]=min(dp[x],dp[x-1]+1);
    for(re int i=1;i<=tot&&p[i]<x;i++)//枚举x的每一个质因数
    if(x%p[i]==0) solve(x/p[i]),dp[x]=min(dp[x],dp[x/p[i]]+1);
}
int main()
{
    T=1;
    while(scanf("%d",&n[T++])!=EOF);
    if(!n[T]) T--;
    int maxx=-1;
    for(re int i=1;i<=T;i++)
        maxx=max(maxx,n[i]);//我们提前把数读进来，把最大的数作为我们筛的上界，这样能省一点时间
    f[1]=1;
    dp[1]=0;//从1到1花费自然是0
    for(re int i=2;i<=maxx;i++)
    {
        if(!f[i]) p[++tot]=i,dp[i]=1;//如果一个数是质数，那么这个数直接除以它本身就得1，所以最小花费为1
        for(re int j=1;j<=tot&&p[j]*i<=maxx;j++)
        {
            f[p[j]*i]=1;
            dp[p[j]*i]=INF;//合数的初始最小花费为INF
            if(i%p[j]==0) break;
        }
    }//欧拉筛常规操作
    for(re int i=1;i<=T;i++)
    {
        if(!n[i]) return 0;
        if(dp[n[i]]!=INF) printf("%d",dp[n[i]]);//已经找到，那么就不用搜了
        else solve(n[i]),printf("%d",dp[n[i]]);
        putchar(10);
    }
}