题解 P2618 【数字工程】

· · 题解

先筛出1~1000000中的所有素数，然后对于每一组数据，从1开始，遍历每一种操作，状态转移方程也就是

dp[i+1]=min(dp[i+1],dp[i]+1)
dp[i*prime[j]]=min(dp[i*prime[j],dp[i]+1)

但是对于同一个n的答案是一样的，所以我们记录下来，下次再遇到n就可以直接输出，如果遇到大于之前所有n的数我们再算，可以节省那么十几ms，不弄也可以过，应该数据比较水。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define For(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
int dp[1000001],prime[1000001],pcnt=0,n;
bool isPrime[1000001];
int main()
{
    int j;
    For(i,2,1000000)
     dp[i]=2147483647;
    isPrime[1]=1;
    For(i,2,1000000)
    {
        if(!isPrime[i])
        {
            j=i+i;
            prime[++pcnt]=i;
            while(j<=1000000)
            {
                isPrime[j]=1;
                j+=i;
            }
        }
    }
    while(scanf("%d",&n)!=EOF)
    {
        if(dp[n]==2147483647)
        For(i,1,n)
        {
            dp[i+1]=min(dp[i]+1,dp[i+1]);
            For(j,1,pcnt)
            {
                if(i*prime[j]>n)
                 break;
                dp[i*prime[j]]=min(dp[i*prime[j]],dp[i]+1);
            }
        }
        cout<<dp[n]<<'\n';
    }
    return 0;
}