D - Make Them Equal

D - Make Them Equal

namespace std;#define int long longconst int mod = 1e9 + 7;const int N= 1e6 + 10;int n, k;int b[N], c[N], v[N];int qmi (int a, int b) { int ans = 1; while (b) { if (b & 1) ans = ans * a; a = a * a; b >>= 1; } return ans;}int get (int tar) { int ans = log(tar) / log(2); if (qmi(2, ans) == tar) return ans; queue q; bool st[N] = {0}; q.push(ans); map dist; dist[ans] = 0; while(q.size()) { auto t = q.front(); q.pop(); if (t == tar) { break; } for (int i = t; i >= 1; i --) { if (t + t / i <= tar) { q.push(t + t / i); dist[t + t / i] = dist[t] + 1; } } } return dist[ans] + ans;}void solve() { cin >> n >> k; int c[N]; memset(c, 0x3f, sizeof c); c[1]= 0; for (int i = 1; i<= 1000; i ++) { for (int j =1; j<= i; j ++) if (i + i / j > i) continue; else c[i + i / j] = min (c[i + i / j], c[i] + 1); } for (int i = 1; i<= n; i ++) { cin >> b[i]; v[i] = c[b[i]]; } for (int i = 1; i <= n; i ++) cin >> c[i]; int f[N] = {0}; for (int i =1; i <= n ;i ++) { for (int j = k; j >= v[i]; j --) f[j] = max (f[j], f[j - v[i]] + c[i]); } cout << f[k] << endl;}signed main () { int t; cin >>t; while (t --) solve(); }

不要define int longlong 这题主要在于预处理部分。我用的是bfs超时了。应该用dp来预处理数组

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。