1 //index不能做变量
2 //h为递增数列
3 //如果我通过h[i]*p[j]得到一个包含p[j]的humble，则下一个包含p[j]的humble则必然从h[i+1]开始，所以可以建立索引p[j]的索引
4 //h[i]=min{p[ j ] * h[ ind[ j ] ]},当然，首先应该先判重，因为2*3==3*2，所以只需判断p[j]*h[ind[j]]是否<=h[i-1]即可
5 #include<iostream>
6 #include<fstream>
7 using namespace std;
8 ifstream fin("humble.in");
9 ofstream fout("humble.out");
10 long h[100001];
11 int p[101];
12 int ind[101];
13 int k,n;
14 int main()
15 {
16 fin>>k>>n;
17 for(int i=1;i<=k;++i)
18 fin>>p[i];
19 h[1]=1;
20 for(int i=1;i<=k;++i)ind[i]=1;
21 for(int i=2;i<=n+1;++i)
22 {
23 int m=0x7fffffff;
24 int q=0;
25 for(int j=1;j<=k;++j)
26 {
27 while(h[ind[j]]*p[j]<=h[i-1])ind[j]++;//第一次wa掉，用的是if，但是这样只能保证排除当前的重复性，下一位也有可能
28 if(h[ind[j]]*p[j]<m)
29 {
30 m=h[ind[j]]*p[j];
31 q=j;
32 }
33 }
34 h[i]=m;
35 ind[q]++;
36 }
37 fout<<h[n+1]<<endl;
38 return 0;
39 }
40
posted on 2008-11-17 22:11
沈鸿飞 阅读(163)
评论(0) 编辑 收藏 引用