usaco_humble.cpp

usaco自己做的1到5章的代码

/*
ID: wangyuc2
PROG: humble
LANG: C++
*/
#include <fstream>
#include <iostream>
#include <cmath>
#include <memory>
#include <iomanip>
#define cin fin
using namespace std;
ifstream fin("humble.in");
ofstream fout("humble.out");
long int np[100005];
int pindex[100];
int prime[100];
int k,n;
int main()
{  
    int i,j,k;
    long int min;
    cin>>k>>n;
    for(i=0;i<k;i++)
    cin>>prime[i];
    memset(pindex,0,sizeof(pindex));
    np[0]=1;
//	np[0]=prime[0];
    for(i=1;i<=n;i++)
    {
        if(i>0) np[i]=0x7fffffff;
        for(j=0;j<k;j++)
        {
            min=pindex[j];
            if(i>0)
            while(np[min]*prime[j]<=np[i-1]) min++;
            pindex[j]=min;
            if(prime[j]*np[pindex[j]]<np[i]) 
            {
                np[i]=prime[j]*np[pindex[j]];               
               // pindex[j]=i;
            }
        }
    }
    fout<<np[n]<<endl;
   // system("PAUSE");
    return 0;
}