第 38 个点是什么牛魔,谁能帮我调一下
  • 板块CF623B Array GCD
  • 楼主XOOR
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/19 21:46
  • 上次更新2024/7/19 23:39:13
查看原帖
第 38 个点是什么牛魔,谁能帮我调一下
450743
XOOR楼主2024/7/19 21:46
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,inf=1e18+100;

int n,A,B,cnt;
int c[N],a[N],pre,suf,sum[N],dp[N];
int cut[50];
map<int,int> vis;

void chkmin(int &x,int y){ return x=x<y?x:y,void();}
void chkmax(int &x,int y){ return x=x>y?x:y,void();}
void div(int x){
	if(!x) return ;
    for(int i=2;i*i<=x;++i){
        if(x%i==0){
            if(!vis[i]) cut[++cnt]=i,vis[i]=1;
            while(x%i==0)x/=i;
        }
    }
    if(x!=1 && !vis[x]) cut[++cnt]=x,vis[x]=1;
}

signed main(){
// 	freopen("in.in","r",stdin);
// 	freopen("out.out","w",stdout);
	scanf("%lld%lld%lld",&n,&A,&B);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	div(a[1]),div(a[n]);
	div(a[1]+1),div(a[n]+1);
	div(a[1]-1),div(a[n]-1);
	int minn=inf;
	for(int i=1;i<=cnt;i++){
		pre=n+1,suf=-1;
		bool ff=1;
		for(int j=0;j<=n+1;j++) sum[j]=0,c[j]=0;
		for(int j=1;j<=n;j++){
			int mod=cut[i];
			if(a[j]%mod==mod-1 || a[j]%mod==1) c[j]=B,sum[j]=sum[j-1]+B;
			else if(a[j]%mod==0) c[j]=0,sum[j]=sum[j-1];
			else chkmin(pre,j),chkmax(suf,j),ff=0,sum[j]=sum[j-1];
		}
		int ans=inf;
		if(ff){
			ans=sum[n];
			for(int j=1;j<n;j++) dp[j]=min(0ll,dp[j-1]+A-c[j]);
			int mnn=inf;
			for(int j=1;j<n;j++) chkmin(mnn,dp[j]);
			dp[1]=inf;
			for(int j=2;j<=n;j++) dp[j]=min(0ll,dp[j-1]+A-c[j]);
			for(int j=2;j<=n;j++) chkmin(mnn,dp[j]);
			chkmin(ans,sum[n]+mnn);
		}else{
			int allsum=sum[n]-(sum[suf]-sum[pre-1])+(suf-pre+1)*A;
			ans=allsum;
			for(int j=1;j<pre;j++) chkmin(allsum,allsum-(sum[pre-1]-sum[j-1])+(pre-j+1)*A);
			for(int j=suf+1;j<=n;j++) chkmin(allsum,allsum-(sum[n]-sum[suf])+(n-suf)*A);
		}
		minn=min(minn,ans);
	}
	printf("%lld",minn);
	return 0;
}
2024/7/19 21:46
加载中...