本文共 1934 字，大约阅读时间需要 6 分钟。

dp问题

#define  _CODE_HDOJ_A1058_DP_#ifdef _CODE_HDOJ_A1058_DP_#include 
   
    #include 
    
     /************************************************************************ f[1] = 1for the factor 2, 3, 5 and 7.1*2 = 2       1*3=3      1*5=5      1*7=72*2 = 4       2*3=6      2*5=10     2*7=143*2 = 6		  3*3=9      3*5=15     3*7=214*2 = 8		  4*3=12     4*5=20     4*7=285*2 = 10	  5*3=15     5*5=25     5*7=356*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
    
   

转载地址：http://frlji.baihongyu.com/