1 条题解
-
0
题意很绕,但实际上很简单。
首先,我们可以用来求出,使用第种龙珠的碎片,能否拼凑出恰好为能量的龙珠,这个复杂度是的。
接下来的问题,就变成如下内容了:
你有个数组,每个数组里有若干个数字,你需要从个数组里面各挑一个数字出来,把他们的和作为这次挑出数字的代价。
问:你能挑出来的第大的数字是多少。
我们称为从第个数组里挑第大的,第个数组里挑第大的,...的方案。
那么,全局最大必定是,我们把它丢进优先队列里去。
那么谁可能是第二大的呢?必然是$(2,1,1,1,1,1,1),(1,2,1,1,1,1,1,1),(1,1,2,1,1,1,1,1),...$中的一项。
因此我们把这种可能丢进优先队列里去,下次拿出来价值最大的方案即可。
一共需要取出次,那么最多丢进去个元素,复杂度。需要注意不要丢重复元素进去哈。
看起来的复杂度,但实际上因为
dp
的过程常数非常小,可以通过。一个彩蛋是,这个
dp
可以通过bitset
优化到#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define N 100005 #define M 100005 #define int long long using namespace std; inline int rd() { int X = 0, w = 0; char ch = getchar(); while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); } while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar(); return w ? -X : X; } int m, k, a[N], b[8]; bool dp[2][M]; int q[8][M], top[8]; void work(int id) { int n = rd(); for (int i = 1; i <= n; ++i) a[i] = rd(); memset(dp, 0, sizeof(dp)); dp[0][0] = 1; // cout<<n*m<<endl; for (int i = 1; i <= n; ++i) { for (int j = 0; j <= m; ++j) dp[i & 1][j] |= dp[(i & 1) ^ 1][j]; for (int j = a[i]; j <= m; ++j) dp[i & 1][j] |= dp[(i & 1) ^ 1][j - a[i]]; } for (int i = 0; i <= m; ++i) if (dp[n & 1][i]) q[id][++top[id]] = i * b[id]; sort(q[id] + 1, q[id] + 1 + top[id]); } struct nod { int id[8], val; bool operator<(nod u) const { if (val != u.val) return val < u.val; for (int i = 1; i <= 7; ++i) if (id[i] != u.id[i]) return id[i] < u.id[i]; return 0; } } ans[N], nxt; priority_queue<nod> Q; map<nod, bool> mp; signed main() { // freopen("dragon.in","r",stdin); // freopen("dragon.out","w",stdout); m = rd(), k = rd(); for (int i = 1; i <= 7; ++i) b[i] = rd(); for (int i = 1; i <= 7; ++i) work(i); nxt.val = 0; for (int i = 1; i <= 7; ++i) nxt.id[i] = top[i], nxt.val += q[i][top[i]]; mp[nxt] = 1; Q.push(nxt); for (int i = 1; i <= k; ++i) { if (Q.empty()) { puts("Stop dreaming XJC!"); return 0; } ans[i] = Q.top(); Q.pop(); for (int t = 1; t <= 7; ++t) if (ans[i].id[t] > 1) { nxt = ans[i]; nxt.id[t]--; nxt.val += q[t][nxt.id[t]] - q[t][nxt.id[t] + 1]; if (mp.count(nxt)) continue; mp[nxt] = 1; Q.push(nxt); } } // for(int i=1;i<=k;++i){ // cout<<ans[i].val<<'\n'; // for(int t=1;t<=7;++t) cout<<q[t][ans[i].id[t]]<<' ';cout<<'\n'; // } cout << ans[k].val << endl; }
- 1
信息
- ID
- 1419
- 时间
- 3000ms
- 内存
- 512MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 110
- 已通过
- 11
- 上传者