建设手机网站的公司,东莞专业网站营销,网站建设自查工作,外贸网站建设注意什么传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
你有nnn个装备槽#xff0c;每个槽里面有cic_ici个力量加成#xff0c;对于每个槽只能选一个力量加成#xff0c;现在给你mmm个力量组合[b1,b2,...,bn][b_1,b_2,...,b_n][b1,b2,...,bn]代表这个力…传送门 文章目录题意思路题意
你有nnn个装备槽每个槽里面有cic_ici个力量加成对于每个槽只能选一个力量加成现在给你mmm个力量组合[b1,b2,...,bn][b_1,b_2,...,b_n][b1,b2,...,bn]代表这个力量组合是不能选择的。问你每个槽选择一个力量之后最大的的力量总和是多少。保证有解。
n≤10,1≤ci≤2e5n\le 10,1\le c_i\le 2e5n≤10,1≤ci≤2e5
cic_ici总和不超过2e52e52e5
思路
可以知道总共的情况就是∏i1nci\prod_{i1}^nc_i∏i1nci由于有解所以这个显然是大于mmm的考虑暴力找状态。
一开始想了个假算法就是每次找所有槽中值最小的显然不对考虑到m≤2e5m\le 2e5m≤2e5所以如果我们直接从当前状态枚举nnn个槽去掉了一个状态将这些状态压入队列中一定可以找到最优解但是队列显然会爆掉考虑到当找到一个能取的集合那么这个集合的子集合都没有用了所以这个时候不需要扩展而且会遍历到很多重复的集合所以需要去重所以这样直接搞就好了复杂度我不是很会算。。
// Problem: D. The Strongest Build
// Contest: Codeforces - Educational Codeforces Round 114 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1574/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int ed[20];
vectorintv[20],ans;
setpairint,vectorints;
mapvectorint,intmp,st;int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d,n);for(int i1;in;i) {int c; scanf(%d,c);while(c--) {int x; scanf(%d,x);v[i].pb(x);}}scanf(%d,m);for(int i1;im;i) {vectorintv;for(int i1;in;i) {int x; scanf(%d,x);v.pb(x);}mp[v]1;} int sum0;for(int i1;in;i) ans.pb(v[i].size());queuevectorintq;q.push(ans); int now0;st[ans]1;while(q.size()) {auto xq.front(); q.pop();if(!mp.count(x)) {int all0;for(int i1;in;i) allv[i][x[i-1]-1];if(allsum) sumall,ansx;continue;}for(int i1;in;i) {if(x[i-1]1) {x[i-1]--;if(st.count(x)) {x[i-1];continue;}q.push(x);st[x]1;x[i-1];} }}for(auto x:ans) coutx ; puts();return 0;
}
/*
3 1 2 3
2 1 5
3 2 4 6
2
3 2 3
2 2 3
*/
