本文共 697 字，大约阅读时间需要 2 分钟。
突破口：状态是线性的，只需一维数组dp[n]。dp[i]表示第i个humble number，humble numbers是递增序列，因此dp[i]>dp[i-1]，且是第一个大于dp[i-1]的，dp[i]一定是由前面某个数乘上2,3,5或7得到的。先用2去乘dp[i-2]及其后面的数，直到2×dp[k]<=dp[i-1]，此时记录下2×dp[k+1]的值，改用3×dp[k]及其后面的数，直到3×dp[l]<=dp[i-1]，记录下3×dp[l+1]的值，再改用5，如此重复，找出其中最小的数，即为dp[i]。
代码如下：
#include#include #include #include #include #define most 2000000000long long dp[5850];long long a[4]={2,3,5,7}; //辅助数组using namespace std;int main(){ int n,i,j,k; long long temp; for(i=1;i<=10;i++) dp[i]=i; for(i=11;i<=5842;i++) { k=0;temp=2000000001; //temp用来记录最终得到的四个数中最小的那一个 for(j=i-2;j>=0;) { if(a[k]*dp[j]>dp[i-1]) { j--; } else { if(a[k]*dp[j+1]
转载地址：http://ybdci.baihongyu.com/