学校网站开发需求,网络营销策划书1000字,网站建设实现用户登录,用源码做网站步骤首先分析不出啥性质#xff0c;所以肯定是暴力优化#x1f605;
常见的暴力优化手段有均摊#xff0c;剪枝#xff0c;数据范围分治#xff08;points#xff09;#xff0c;答案值域分析之类的。
比较经典的题目是 CF1870E Another MEX Problem#xff0c;可以用剪枝…首先分析不出啥性质所以肯定是暴力优化
常见的暴力优化手段有均摊剪枝数据范围分治points答案值域分析之类的。
比较经典的题目是 CF1870E Another MEX Problem可以用剪枝和分析值域两种方法通过
考虑剪枝这个大佬 是剪枝高手大家快去膜拜他
首先设 g gcd 1 ≤ i ≤ n a i g\gcd_{1\le i\le n} a_i ggcd1≤i≤nai然后对每个 a i a_i ai只保留 g g g中的质因数。发现此时本质不同的 a i a_i ai比较少并且本质不同的质因数也比较少考虑从这两方面入手
记质因数数目为 M M M a i a_i ai的状态数为 m m m显然 M ≤ 11 M\le 11 M≤11 m m m不太清楚但是可以感性发现不会很大
发现对于相同的 a i a_i ai只需要保留前 M M M个较小的 e i e_i ei即可后面的都用不上。
同时注意到被操作的数不会超过 M M M因此 D P DP DP复杂度为 O ( 3 M m M 2 ) O(3^MmM^2) O(3MmM2)
每次只加入一个 a i a_i ai太浪费了可以考虑一次将相同的 a i a_i ai一起加进去然后记录需要选择的 a i a_i ai数目的最小值。这样组外 D P DP DP的复杂度为 O ( 3 M m M ) O(3^MmM) O(3MmM)组内 D P DP DP的复杂度为 O ( 3 M m ) O(3^Mm) O(3Mm)。
当 M M M取遍所有值时最大计算量在 1 0 8 10^8 108左右可以通过。
#includebits/stdc.h
#define fi first
#define se second
#define pb push_back
#define ll long long
#define db double
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N1e65;
int n,cnt;
ll K,a[N],nums[N],e[N],g,res;
int M;
ll prime[15];
vectorllv[15005];
ll gcd(ll x,ll y){return y0?x:gcd(y,x%y);
}
int get(ll x){return lower_bound(nums1,nums1cnt,x)-nums;
}
void dfs(int u,ll mul){if(uM){nums[cnt]mul;return;}while(mul1000000000000/prime[u]){mul*prime[u],dfs(u1,mul);}
}
ll now[111][12],nxt[111][12],sm[12];
int dp[111],h[111];
ll b[15];
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinnK;for(int i1;in;i)cina[i],ggcd(g,a[i]);for(int i1;in;i)cine[i];ll tmpg;for(int i2;itmp/i;i){if(tmp%i0){prime[M]i;while(tmp%i0)tmp/i;}}if(tmp1)prime[M]tmp;dfs(0,1),sort(nums1,nums1cnt);for(int i1;in;i){ll tmp21;for(int j0;jM;j){while(a[i]%prime[j]0)a[i]/prime[j],tmp2*prime[j];}v[get(tmp2)].pb(e[i]);}memset(now,0x3f,sizeof now),now[0][0]0;for(int i1;icnt;i){if(v[i].size()0)continue;sort(v[i].begin(),v[i].end());if(v[i].size()M)v[i].resize(M);for(int j0;jv[i].size();j)sm[j1]sm[j]v[i][j];ll tmpnums[i];for(int j0;jM;j){b[j]1;while(tmp%prime[j]0)b[j]*prime[j],tmp/prime[j];}for(int j0;j1M;j){for(int k0;kM;k){nxt[j][k]now[j][k];}}for(int j1;j1M;j){h[j]0,dp[j]114514;ll mul1;for(int k0;kM;k){if(jk1)mul*b[k];}if(mulK)h[j]1;for(int kj;k;k(k-1)j){if(h[k])dp[j]min(dp[j],dp[j-k]1);}if(dp[j]v[i].size()){int s(1M)-1-j;for(int ks;;k(k-1)s){for(int l0;lM;l){if(now[k][l]!inf){nxt[kj][ldp[j]]min(nxt[kj][ldp[j]],now[k][l]sm[dp[j]]);}}if(k0)break;}}}for(int j0;j1M;j){for(int k0;kM;k){now[j][k]nxt[j][k];}}}ll resinf;for(int i0;iM;i)if(now[(1M)-1][i]!inf)resmin(res,now[(1M)-1][i]*i);cout(resinf?-1:res);
}
