1028: 数字工程
题目描述
ACM实验室开启了一个数字工程项目，希望把正整数n通过一些特殊方法变成1。
可采用的方法有：（1）减去1；（2）除以它的任意一个素因子。 每操作一次消耗一个单位的能量。
问，把n变成1最少需要消耗多少能量？
输入
多组测试
对于每组测试，输入正整数n (1<=n<=1,000,000)
输出
输出最少消耗的能量
样例输入
14
样例输出
02
提示
来源
题目类型：线性DP
算法分析：使用数组dp[i]表示正整数i变成1时需要消耗的最小能量，状态转移方程(我为人人型)为：dp[i*k] = min (dp[i*k], dp[i] +1)和dp[i+1] = min (dp[i+1], dp[i] + 1)，其中k表示素数。初始化为：dp[i] = INF，dp[1] =0。然后先打出素数表，之后可以直接递推求解dp数组，最终查表即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1000000 + 666; bool is_p[maxn]; int prime[maxn], len, dp[maxn]; int main() { // ifstream cin ("aaa.txt"); memset (is_p, true, sizeof (is_p)); len = 0; for (int i = 2; i <= maxn - 66; i++) { if (is_p[i]) { prime[len++] = i; for (int j = 2; j * i <= maxn- 66; j++) is_p[j*i] = false; } } fill (dp, dp + maxn, INF); dp[1] = 0; for (int i = 1; i <= 1000000; i++) { for (int j = 0; j < len; j++) { if (prime[j] * i > 1000000) break; dp[i*prime[j]] = min (dp[i*prime[j]], dp[i] + 1); } dp[i+1] = min (dp[i+1], dp[i] + 1); } int n; while (cin >> n) { cout << dp[n] << endl; } return 0; } |
- « 上一篇：lightoj1427
- xdu1029：下一篇 »