CF1103D Professional layer dp
正解:dp
解题报告:
首先不难想到求个gcd,然后把gcd质因数分解成p1w1*p2w2*p3w3*...*pmwm
显然只要满足对每个p有一个ai%pj!=0就好,也就是说对每个pj找出一个ai然后代价最小就好
然后这时候就考虑dp
先考虑最简单的,f[i][x][s]:dp到第i个了,改了x个,p的状态为s的最小花费
然后直接枚举删哪个质因子集,判是否合法(<=k)即可
这时候发现复杂度不太对,是O(nm3m)不会分析复杂度不要问我为什么是这个式子,,,
但反正是跑不过去的这个是可以发现的
因为可以发现m<=11(2*3*5*7*11*13*17*19*23*29*31)嘛,这样显然是会T的
所以考虑怎么优化
考虑到我们最开始的那个dp能有一个小优化
那个dp的顺序显然是for(i)for(x)for(S)for(T),其中S指的是原来的状态,T指的是增加的状态嘛
这里可以考虑到,对质因数的倍数的集合,我们只要保留前m个就欧克了,后面显然都是浪费(这里关于集合这个词可能比较难get,,,指的是对每个数,有意义的地方只在那些单纯由gcd的质因数构成的数,所以把每个数的最大的这个有用数拿出来,把这个有用数相当的数就可以作为一个集合辣!(还是说得不太清楚的样子QAQ
继续优化,可以发现对于每个状态其实也只要保留前m个就欧克了
所以对每个状态也只要枚m次,超过了就不枚了
所以考虑改变枚举顺序,先枚T,然后枚T的补集的子集S
然后这里先港下枚举集合的正确姿势
如果现在是要枚举集合满足j是k的子集
显然首先肯定要已知一个集合,就分类讨论下,看是已知j还是已知k
如果是已知j了,就是说枚举包含某个集合的集合,就可以for(ri k=(j+1)|j;k<=S;k=(k+1)|j)
(因为,一般要枚举集合之类的都是在dp转移中,所以就不考虑k=j的情况了QAQ
然后如果是已知k了,就是说枚举某个集合的子集,就可以for(ri j=(k-1)&k;j;j=(j-1)&k)
原理还是挺显然的?实在无法理解手动模拟下就能get辣
然后好像就差不多了?
#include<bits/stdc++.h> using namespace std; #define fr first #define sc second #define il inline #define ll long long #define gc getchar() #define rl register ll #define rc register char #define rb register bool #define rp(i,x,y) for(rl i=x;i<=y;++i) #define my(i,x,y) for(rl i=x;i>=y;--i) const ll N=1e6+10,M=15; ll n,K,gcdd,fac[M],fac_cnt,f[M][1<<M],S,poww[M]={1},as,inf; bool vis[1<<M]; struct node{ll a,e;}nod[N]; map< ll,vector<ll> >Mp; il ll read() { rc ch=gc;rl x=0;rb y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=gc; if(ch=='-')ch=gc,y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc; return y?x:-x; } il ll gcd(rl gd,rl gs){return gs?gcd(gs,gd%gs):gd;} int main() { // freopen("ayg.in","r",stdin);freopen("ayg.out","w",stdout); n=read();K=read();rp(i,1,n)nod[i].a=read();rp(i,1,n)nod[i].e=read();gcdd=nod[1].a;rp(i,2,n)gcdd=gcd(gcdd,nod[i].a); if(!(gcdd^1))return printf("0\n"),0; for(rl i=2;i*i<=gcdd;++i)if(!(gcdd%i)){fac[fac_cnt++]=i;while(!(gcdd%i))gcdd/=i;} if(gcdd^1)fac[fac_cnt++]=gcdd; rp(i,1,n){rl tmp=1;rp(j,0,fac_cnt-1)while(!(nod[i].a%fac[j]))tmp*=fac[j],nod[i].a/=fac[j];Mp[tmp].push_back(nod[i].e);} memset(f,63,sizeof(f));inf=as=f[0][0];f[0][0]=0; S=(1<<fac_cnt)-1;rp(i,1,fac_cnt)poww[i]=poww[i-1]<<1; for(auto i:Mp) { ll x=i.fr;sort(i.sc.begin(),i.sc.end());if(i.sc.size()>fac_cnt)i.sc.resize(fac_cnt); rp(j,0,S){rl y=x,z=1;rp(k,0,fac_cnt-1)if(j&poww[k])while(!(y%fac[k]))y/=fac[k],z*=fac[k];vis[j]=(z<=K);} for(auto j:i.sc) { bool flg=0; my(k,fac_cnt-1,0) rp(p,0,S) if(f[k][p]<inf) for(rl q=(p+1)|p;q<=S;q=(q+1)|p)if(vis[q^p])if(f[k+1][q]>f[k][p]+j)flg=1,f[k+1][q]=f[k][p]+j; if(!flg)break; } } rp(i,0,fac_cnt)if(f[i][S]<inf)as=min(as,f[i][S]*i);if(as^inf)printf("%lld\n",as);else printf("-1\n"); return 0; }