Luogu P2723 丑数 Humble Numbers

太巧妙了，想了好久都没想出来，居然只是道黄题。。。

用s[j]储存每个数的下界，以大大减少枚举次数；从较小的数据入手，分析解题思路，优化枚举顺序从而优化复杂度。

#include<iostream>
#include<climits>

using namespace std;

const int Maxn = 1e5+10;
int f[Maxn] = {1},p[110],s[110];
int n,k,m;

int main(){
    cin >> k >> n;
    for(int i = 1;i <= k;i++)cin >> p[i];
    for(int i = 1;i <= n;i++){
        m = INT_MAX;
        for(int j = 1;j <= k;j++){
            while(f[s[j]]*p[j] <= f[i-1])s[j]++;
            if(f[s[j]]*p[j] < m)m = f[s[j]]*p[j];
        }
        f[i] = m;
    }
    cout << f[n] << '
';
return 0;
}