这个模拟也是真心不会做啊,第一次做超时,然后看了标程..
code:
/* ID:yueqi LANG:C++ TASK:humble */ #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <limits.h> #include <vector> #include <bitset> #include <string> #include <cstdio> #include <cstring> #include <fstream> #include <string.h> #include <iostream> #include <algorithm> #define Si set<int> #define LL long long #define pb push_back #define PS printf(" ") #define Vi vector<int> #define LN printf("\n") #define lson l,m,rt << 1 #define rson m+1,r,rt<<1|1 #define SD(a) scanf("%d",&a) #define PD(a) printf("%d",a) #define SET(a,b) memset(a,b,sizeof(a)) #define FF(i,a) for(int i(0);i<(a);i++) #define FD(i,a) for(int i(a);i>=(1);i--) #define FOR(i,a,b) for(int i(a);i<=(b);i++) #define FOD(i,a,b) for(int i(a);i>=(b);i--) #define readf freopen("humble.in","r",stdin) #define writef freopen("humble.out","w",stdout) const int maxn = 100001; const long long BigP=999983; const long long INF = 0x5fffffff; const int dx[]={-1,0,1,0}; const int dy[]={0,1,0,-1}; const double pi = acos(-1.0); const double eps= 1e-7; using namespace std; LL dp[maxn]; int prime[101],pos[101]; int N,M,num; int main(){ readf; writef; SD(N);SD(M); FOR(i,1,N) SD(prime[i]); dp[0]=1; LL minn; int minnpos; while(num<M){ minn=100*INF; minnpos=-1; FOR(i,1,N){ while(prime[i]*dp[pos[i]]<=dp[num]) pos[i]++; if(prime[i]*dp[pos[i]]<minn){ minn=prime[i]*dp[pos[i]]; minnpos=i; } } dp[++num]=minn; pos[minnpos]++;//? } printf("%lld\n",dp[M]); return 0; }