首页 > 代码库 > hdu-acm stepsHumble Numbers

hdu-acm stepsHumble Numbers

2024-11-18 00:33:39   202人阅读

这是我做的第六道动态规划水题，对动态规划差不多有了一个大致的概念。动态规划有几个关键因素，第一是最优子结构，第二是状态和状态转移方程。整个过程都是以  最优  为中心的。因此在状态转移方程中常涉及到几个子状态的最优化的判断。这道题既采用了递堆的思想，又采用了一点动态规划的思想。状态转移方程为：f[i]=min{2*f[p],3*f[q],5*f[r],7*f[s]};

技术分享
 1 #include"iostream" 2 #include"stdio.h" 3 #include"algorithm" 4 #include"string.h" 5 #include"cmath" 6 #include"ctype.h" 7 #define mx 10005 8 using namespace std; 9 long long dp[mx];10 int p,q,r,s;11 int min(int a,int b,int c,int d)12 {13     int mi=a;14     if(b<mi) mi=b;15     if(c<mi) mi=c;16     if(d<mi) mi=d;17 18     if(a==mi) p++;19     if(b==mi) q++;20     if(c==mi) r++;21     if(d==mi) s++;22 23     return mi;24 }25 int main()26 {27     int i,n;28     dp[1]=1;29     p=q=r=s=1;30     for(i=2;i<=5842;i++)31     {32         dp[i]=min(2*dp[p],3*dp[q],5*dp[r],7*dp[s]);33     }34     while(cin>>n,n)35     {36         if(n%10==1&&n%100!=11) cout<<"The "<<n<<"st humble number is "<<dp[n]<<"."<<endl;37         else if(n%10==2&&n%100!=12) cout<<"The "<<n<<"nd humble number is "<<dp[n]<<"."<<endl;38         else if(n%10==3&&n%100!=13) cout<<"The "<<n<<"rd humble number is "<<dp[n]<<"."<<endl;39         else cout<<"The "<<n<<"th humble number is "<<dp[n]<<"."<<endl;40     }41     return 0;42 }
View Code

 

hdu-acm stepsHumble Numbers


联系
我们