找一个最小的 p*h 比最后一个已经找出来的humble数大 那它肯定是下一个humble数 依次找下去
1 /* 2 ID:shangca2 3 PROG:humble 4 LANG:C++ 5 */ 6 #include <iostream> 7 #include<cstdio> 8 #include<cstring> 9 #include<algorithm> 10 #include<stdlib.h> 11 #define INF 0x7fffffff 12 using namespace std; 13 long long num[110],mi,hum[100010],f[110]; 14 int main() 15 { 16 freopen("humble.in","r",stdin); 17 freopen("humble.out","w",stdout); 18 int i,j,k,n,m,g=0,kk=0; 19 cin>>k>>n; 20 for(i = 1; i <= k ; i++) 21 { 22 cin>>num[i]; 23 } 24 memset(hum,0,sizeof(hum)); 25 hum[0] =1; 26 while(kk<n) 27 { 28 mi = INF; 29 for(i = 1 ; i <= k ; i++) 30 { 31 while(num[i]*hum[f[i]]<=hum[kk]) 32 f[i]++; 33 if(num[i]*hum[f[i]]<mi) 34 mi = num[i]*hum[f[i]]; 35 } 36 kk++; 37 hum[kk] = mi; 38 } 39 cout<<hum[n]<<endl; 40 return 0; 41 }