posts - 2,  comments - 0,  trackbacks - 0
 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 沈鸿飞 阅读(172) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2008年11月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

常用链接

留言簿(3)

随笔档案

文章档案

acm

搜索

  •  

最新评论

阅读排行榜

评论排行榜