洛谷题号:P2723
参考题解:作者: redbag 管理员 更新时间: 2016-08-01 23:15 https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P2723
这个暴力还是有一定思想的,一般人根本想不到的…………
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | #include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<string> #include<cassert> #include<map> #include<queue> using namespace std; int k, n; long long a[105], s[200000], f[200000]; int main(){ ios::sync_with_stdio(false); cin >> k >> n; for (int i = 1; i <= k; i++){ cin >> a[i]; } f[0] = 1; for (int i = 1; i <= n; i++){ long long m = 2e10; for (int j = 1; j <= k; j++){ while (a[j] * f[s[j]] <= f[i - 1])s[j]++; m = min(a[j] * f[s[j]], m); } f[i] = m; } cout << f[n] << endl; } |