题目链接
很巧妙的一个递推，因为只有2,3,5,7构成，那么后面的数一定是2,3,5,7的倍数，所以可以直接枚举那个最小，用四个变量来维护2,3,5,7分别算到几了。
dp【i】 = min(2 * dp[p2], 3 * dp[p3], 5 * dp[p5], 7 * dp[p7]);
/************************************************************************* > File Name: 2.cpp > Author: Howe_Young > Mail: 1013410795@qq.com > Created Time: 2015年08月17日 星期一 10时55分58秒 ************************************************************************/#include#include #include #include #include #include #define min4(a, b, c, d) min(min(a, b), min(c, d))using namespace std;typedef long long ll;const int maxn = 6000;ll dp[maxn];void init(){ int p2 = 1, p3 = 1, p5 = 1, p7 = 1; dp[1] = 1; for (int i = 2; i <= 5842; i++) { dp[i] = min4(2 * dp[p2], 3 * dp[p3], 5 * dp[p5], 7 * dp[p7]); if (dp[i] == 2 * dp[p2]) p2++; if (dp[i] == 3 * dp[p3]) p3++; if (dp[i] == 5 * dp[p5]) p5++; if (dp[i] == 7 * dp[p7]) p7++; }}int main(){ int n; init(); while (cin >> n && n) { int t = n % 10; if (t == 1 && n % 100 != 11) printf("The %dst humble number is ", n); else if (t == 2 && n % 100 != 12) printf("The %dnd humble number is ", n); else if (t == 3 && n % 100 != 13) printf("The %drd humble number is ", n); else printf("The %dth humble number is ", n); printf("%I64d.\n", dp[n]); } return 0;}
还有一个，这个题目给的数很大，其实根本没有那么大，同样可做
/************************************************************************* > File Name: 3.cpp > Author: Howe_Young > Mail: 1013410795@qq.com > Created Time: 2015年08月17日 星期一 11时28分41秒 ************************************************************************/#include#include #include #include #include #include #define min3(a, b, c) min(a, min(b, c))using namespace std;typedef long long ll;const int maxn = 10000;ll d[maxn];ll dp(ll a, ll b, ll c, ll n){ d[0] = 1; int p1 = 0, p2 = 0, p3 = 0; for (int i = 1; i <= n; i++) { d[i] = min3(a * d[p1], b * d[p2], c * d[p3]); if (d[i] == a * d[p1]) p1++; if (d[i] == b * d[p2]) p2++; if (d[i] == c * d[p3]) p3++; } return d[n];}int main(){ ll p1, p2, p3, i; while (~scanf("%I64d %I64d %I64d %I64d", &p1, &p2, &p3, &i)) { printf("%I64d\n", dp(p1, p2, p3, i)); } return 0;}