题解 P2618 【数字工程】

· · 题解

可能会有更好的阅读体验

这道题的做法其他的各位巨佬们都已经讲得很详细了，我这里来教大家一些提高自己代码效率的方法（仅限此题）。

第一阶段：

这里建议看一下这篇题解，非常的简单易懂，里面的代码就是第一阶段需要打出的代码。

但是这个代码太慢了，要144ms，所以我们考虑优化。

第二阶段：

我不知道为什么大部分的DP题解都没有想到直接把数据范围内的所有答案全部预处理出来，之后每次输出直接输出答案即可，而不是每输入一个进行一次操作，那样子会浪费大部分的时间。

这里给出第二阶段的代码：

#include <bits/stdc++.h>
using namespace std;
int prime[100005],isprime[1000005],dp[1000005],n,cnt;
int main() 
{
    for (int i = 2; i <= 1000000; i++)
    {
        dp[i] = 2147483640;
        if (isprime[i] == 0)
        {
            prime[++cnt] = i;
            for (int j = 2; j * i <= 1000000; j++)
                {
                    isprime[i * j] = 1;
                }
        }
    }
    for (int i = 1; i <= 1000000; i++)//这里直接预处理。
    {
        dp[i + 1] = min(dp[i] + 1,dp[i + 1]);
        for (int j = 1; j <= cnt; j++)
            {
                if (i * prime[j] > 1000000) break;
                dp[i * prime[j]] = min(dp[i * prime[j]],dp[i] + 1);
            }
    }
    while(scanf("%d",&n) != EOF) printf("%d\n",dp[n]);
    //直接输出。
    return 0;
}

AC记录

虽然这份代码速度快到了106ms，但是依旧没有拿到这道题的最优解，我们考虑第三阶段的优化。

第三阶段：

我们发现第二阶段的代码的确快了很多，但是我们很快又发现了一个问题——并不是所有数都需要预处理的。

所以我们考虑先把输入输进来，取其中的最大值，只预处理到这个值即可。

第三阶段的代码：

#include <bits/stdc++.h>
using namespace std;
int prime[100005],isprime[1000005],dp[1000005],n,cnt,maxa,a[1000005],sum;
int main() 
{
    while(scanf("%d",&a[++sum]) != EOF) maxa = max(maxa,a[sum]);
    //取输入中的最大值。
    for (int i = 2; i <= 1000000; i++)
    {
        dp[i] = 2147483640;
        if (isprime[i] == 0)
        {
            prime[++cnt] = i;
            for (int j = 2; j * i <= 1000000; j++)
                {
                    isprime[i * j] = 1;
                }
        }
    }
    for (int i = 1; i < maxa; i++)//只预处理到这个最大值。
    {
        dp[i + 1] = min(dp[i] + 1,dp[i + 1]);
        for (int j = 1; j <= cnt; j++)
            {
                if (i * prime[j] > 1000000) break;
                dp[i * prime[j]] = min(dp[i * prime[j]],dp[i] + 1);
            }
    }
    for (int i = 1; i < sum; i++) printf("%d\n",dp[a[i]]);
    return 0;
}

AC记录

第四阶段：

虽然你有可能会觉得这一阶段是用来凑数的，但我当时就是按照这几个阶段卡上来的。

第三阶段的代码只能拿到次优解，我们还得优化。

按照第三阶段的思路，我们发现还有一个地方可以优化：

for (int j = 1; j <= cnt; j++)
    {
        if (i * prime[j] > 1000000) break;//这里只要执行到maxa就行了。
        dp[i * prime[j]] = min(dp[i * prime[j]],dp[i] + 1);
    }

于是我们就得到了最终的代码，也就是获得了当时的最优解的代码：

#include <bits/stdc++.h>
using namespace std;
int prime[100005],isprime[1000005],dp[1000005],n,cnt,maxa,a[1000005],sum;
int main() 
{
    while(scanf("%d",&a[++sum]) != EOF) maxa = max(maxa,a[sum]);
    for (int i = 2; i <= 1000000; i++)
    {
        dp[i] = 2147483640;
        if (isprime[i] == 0)
        {
            prime[++cnt] = i;
            for (int j = 2; j * i <= 1000000; j++)
                {
                    isprime[i * j] = 1;
                }
        }
    }
    for (int i = 1; i < maxa; i++)
    {
        dp[i + 1] = min(dp[i] + 1,dp[i + 1]);
        for (int j = 1; i * prime[j] <= maxa; j++)//这里是优化。
            {
                dp[i * prime[j]] = min(dp[i * prime[j]],dp[i] + 1);
            }
    }
    for (int i = 1; i < sum; i++) printf("%d\n",dp[a[i]]);
    return 0;
}

AC记录