CodeForces 623B Array GCD

2019-11-08 02:50:03

字体：大中小

来源：转载

供稿：网友

CodeForces 623B Array GCD

数论 dp

传送门：HustOJ

传送门：CodeForce

题意

给你个数组，允许进行两种操作各最多一次。第一种操作，删除某一区间内所有数。注意不能删全部的数。代价是个数*a。第二种操作，对某些数进行+1或-1。注意可以部分加1部分减1。代价是每个数b。问你使剩下数公约数大于1所需花费的最小代价。

思路

%%%

由于不能全删完，所以至少会有一个数留着，这个数肯定会是头一个或最后一个，最大公约数肯定是在选中的这个数最后状态中的一个约数，而我们只要先枚举这个数是多少（一共6种），然后枚举他的素因子，用dp顺推即可。

{a1+1 $a_1+1$ ， a1 $a_1$ ， a1−1 $a_1-1$ ， an+1 $a_n+1$ ， an $a_n$ ，an−1 $a_n-1$ }一共6个数，进行质因数分解6次，每次枚举所有质因子，递推计算代价，最后加上处理 a1 $a_1$ 或 an $a_n$ 的代价。

dp[MAXN][3];//第二位 0表示没开始删 1表示正在删 2表示结束了删

注意状态转移的方式。

代码

#include <cstdio>#include <cstdlib>#include <iostream>#include <algorithm>#include <string>#include <cstring>#include <vector>#include <cmath>#include <queue>#include <stack>#define _ ios_base::sync_with_stdio(0);cin.tie(0);#define M(a,b) memset(a,b,sizeof(a));using namespace std;const int MAXN=1000005;const int oo=0x3f3f3f3f;typedef long long LL;const LL loo=4223372036854775807ll;typedef long double LB;int num[MAXN];bool isPRime[MAXN];vector<int> prime;vector<int> fact;void GetPrime(){ M(isprime, 0); for(int i=2; i<MAXN; i++) if(isprime[i]==0) { for(int j=2; i<MAXN/j; j++) isprime[i*j]=1; prime.push_back(i); }}void GetFactor(int x){ fact.clear(); for(int i=0;i<prime.size();i++) { if(x%prime[i]==0) fact.push_back(prime[i]); while(x%prime[i]==0) x/=prime[i]; if(x==1) break; } if(x!=1) fact.push_back(x);//注意最后剩的x要不是1，那一定是个大质数}LL dp[MAXN][3];//第二位 0表示没开始删 1表示正在删 2表示结束了删LL cost1, cost2;LL deal(int s, int e, int fa){ M(dp, 0x3f);dp[s-1][0]=0; for(int i=s;i<=e;i++) { dp[i][1]=min(dp[i-1][0], dp[i-1][1])+cost1; if(num[i]%fa==0) { dp[i][0]=dp[i-1][0]; dp[i][2]=min(dp[i-1][2], dp[i-1][1]); } else if((num[i]+1)%fa==0||(num[i]-1)%fa==0) { dp[i][0]=dp[i-1][0]+cost2; dp[i][2]=min(dp[i-1][1], dp[i-1][2])+cost2; } } LL tt=min(dp[e][0], dp[e][1]); return min(tt, dp[e][2]);}int main(){ _ int n; GetPrime(); while(cin>>n) { cin>>cost1>>cost2; for(int i=1;i<=n;i++) cin>>num[i]; LL res=loo; for(int t=-1;t<2;t++) { GetFactor(num[1]+t); for(int i=0;i<fact.size();i++) res=min(res, deal(2, n, fact[i])+(t==0 ? 0 : cost2)); GetFactor(num[n]+t); for(int i=0;i<fact.size();i++) res=min(res, deal(1, n-1, fact[i])+(t==0 ? 0 : cost2)); } cout<<res<<endl; } return 0;}

上一篇：[省选] [BFS] HLOI2016Day1 黑白棋

下一篇：STL 队列queue的使用

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注