CodeForces 623B Array GCD

2019-11-08 02:50:03

字體：大中小

來源：轉(zhuǎn)載

供稿：網(wǎng)友

CodeForces 623B Array GCD

數(shù)論 dp

傳送門：HustOJ

傳送門：CodeForce

題意

給你個數(shù)組，允許進(jìn)行兩種操作各最多一次。第一種操作，刪除某一區(qū)間內(nèi)所有數(shù)。注意不能刪全部的數(shù)。代價是個數(shù)*a。第二種操作，對某些數(shù)進(jìn)行+1或-1。注意可以部分加1部分減1。代價是每個數(shù)b。問你使剩下數(shù)公約數(shù)大于1所需花費(fèi)的最小代價。

思路

%%%

由于不能全刪完，所以至少會有一個數(shù)留著，這個數(shù)肯定會是頭一個或最后一個，最大公約數(shù)肯定是在選中的這個數(shù)最后狀態(tài)中的一個約數(shù)，而我們只要先枚舉這個數(shù)是多少（一共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個數(shù)，進(jìn)行質(zhì)因數(shù)分解6次，每次枚舉所有質(zhì)因子，遞推計算代價，最后加上處理 a1 $a_1$ 或 an $a_n$ 的代價。

dp[MAXN][3];//第二位 0表示沒開始刪 1表示正在刪 2表示結(jié)束了刪

注意狀態(tài)轉(zhuǎn)移的方式。

代碼

#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，那一定是個大質(zhì)數(shù)}LL dp[MAXN][3];//第二位 0表示沒開始刪 1表示正在刪 2表示結(jié)束了刪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的使用