luogu2618 数字工程 DP

题目大意：ACM实验室开启了一个数字工程项目，希望把正整数n通过一些特殊方法变成1。可采用的方法有：（1）减去1；（2）除以它的任意一个素因子。 每操作一次消耗一个单位的能量。问，把n变成1最少需要消耗多少能量？

定义\(f(i)\)为将i变为1所需要的能量，则有递归式：

\[\min({f(i-1)+1,\min_{质数p|i}({f(i/p)+1})})
\]

用刷表法解决即可。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAX_N = 1000010, MAX_PRIME = 1000000, INF = 0x3f3f3f3f;

int F[MAX_N], Primes[MAX_PRIME];

int N;

void GetPrime(int *prime, int n)

{

	static bool NotPrime[MAX_PRIME];

	memset(NotPrime, false, sizeof(NotPrime));

	int primeCnt = 0;

	for (int i = 2; i <= n; i++)

	{

		if (!NotPrime[i])

			prime[primeCnt++] = i;

		for (int j = 0; j < primeCnt; j++)

		{

			if (i*prime[j] > n)

				break;

			NotPrime[i*prime[j]] = true;

			if (i%prime[j] == 0)

				break;

		}

	}

}

int DP(int n)

{

	if (n <= N)

		return F[n];

	for (int i = 1; i <= n; i++)

	{

		F[i + 1] = min(F[i + 1], F[i] + 1);

		for (int j = 1; Primes[j] <= n / i; j++)

			F[i * Primes[j]] = min(F[i * Primes[j]], F[i] + 1);

	}

	N = n;

	return F[n];

}

int DP_Dfs(int n)

{

	if (F[n] < INF)

		return F[n];

	F[n] = DP_Dfs(n - 1) + 1;

	for (int i = 1; Primes[i] <= n; i++)

		if (n%Primes[i] == 0)

			F[n] = min(F[n], DP_Dfs(n / Primes[i]) + 1);

	return F[n];

}

int main()

{

	GetPrime(Primes + 1, MAX_N);//易忘点：MAX_N，而不是MAX_PRIME

	memset(F, INF, sizeof(F));

	N = 1;

	F[N] = 0;

	int n;

	while (~scanf("%d", &n))

		printf("%d\n", DP(n));

	return 0;

}