dp问题
#define _CODE_HDOJ_A1058_DP_ #ifdef _CODE_HDOJ_A1058_DP_ #include <stdio.h> #include <iostream> /************************************************************************ f[1] = 1 for the factor 2, 3, 5 and 7. 1*2 = 2 1*3=3 1*5=5 1*7=7 2*2 = 4 2*3=6 2*5=10 2*7=14 3*2 = 6 3*3=9 3*5=15 3*7=21 4*2 = 8 4*3=12 4*5=20 4*7=28 5*2 = 10 5*3=15 5*5=25 5*7=35 6*2 = 12 6*3=18 6*5=30 6*7=42 . . . . . . . . . . . . and the Humble number sequence is : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27... 1)if f[j] is a humble number, so f[j]*2, f[j]*3, f[j]*5, f[j]*7 are humbles. 2)if f[i] is humble number, so it must be derived from f[j]*2 or f[k]*3 or f[l]*5 or f[m]*7,(j,k,l,m) < i. 3)f sequence is ascending order,so trans function: f[i] = min{f[p2]*2, f[p3]*3, f[p5]*5, f[p7]*7} ************************************************************************/ const int N = 5842; const int Tw = 2; const int Tr = 3; const int Fi = 5; const int Se = 7; int dp[N+1]; inline int Min2(int a, int b) { return a < b ? a : b; } inline int Min4(int a, int b, int c, int d) { return Min2(Min2(a,b), Min2(c, d)); } void PrintOut(int n) { printf("The %d", n); int last = n%100; if(last==13 || last==12 || last==11) { printf("th humble number is %d.\n", dp[n]); return ; } last = n%10; if(last == 1) printf("st"); else if(last == 2) printf("nd"); else if(last == 3) printf("rd"); else printf("th"); printf(" humble number is %d.\n", dp[n]); } void Calcul() { int p2, p3, p5, p7; p2 = p3 = p5 = p7 = 1; dp[1] = 1; for (int i = 2; i <= N; ++i) { dp[i] = Min4(dp[p2] * Tw, dp[p3] * Tr, dp[p5] * Fi, dp[p7] * Se); //dp[i] = base * multiple if(dp[i] == dp[p2] * Tw) p2++; if(dp[i] == dp[p3] * Tr) p3++; if(dp[i] == dp[p5] * Fi) p5++; if(dp[i] == dp[p7] * Se) p7++; } } int main() { int n; Calcul(); while (scanf("%d", &n), n) { PrintOut(n); } return 0; } #endif