题意：
给n个数，通过两种操作
操作1：删除一段连续区间，代价 区间长度*b ，只能 选一个区间
操作2：让一个数增加或减少1，一个数只能change 1次。每个数的change花费为a
【不能删除所有的数】 问你最小花费是多少使得 最后所有数的最大公约数大于1.
【不能删除所有的数】.是这个题的切入点，因为不能删除所有数，并且删除区间又是连续的，我们可以知道最后一定会留下a[1]或者a[n]，因此我们只需要暴力枚举最后答案为第一个数和最后一个数，及他们加减一共6个数的质因子即可
对于某个因子k，
我们最终的花费 ans= pre[i-1]+(j-i+1)*b +back[j+1];
pre[] 表示1到i-1里面用change使所有数合法的代价，back是使j+1到n的数都合法的change代价
中间的自然就是删除区间的代价
上式变化一下 变成ans=(pre[i-1] + (1-i)*a + a*j+back[j+1] );
显然是关于i,j的两部分 ，我们称i的部分为ff[i]
我们只需要预处理好 关于i 的部分的前缀最小值，然后枚举j的部分就好了
即： 对 固定的一个j，要找到一个i使得ans最小的话，需要从ff[1]到ff[j-1]中选一个最小的ff[i],就能得到一个最小的ans.
因此：
[cpp] view plain copy <span style="font-size:18px;"> temp1[0]=1e16; for (i=1;i<=n+1;i++) //预处理temp[i]表示,对于固定的j,从1到i选一个i使得ans最小的i temp1[i]=min(temp1[i-1],pre[i-1]+(1-i)*a); </span> 然后枚举j 就能得到min——ans了
[cpp] view plain copy #include <cstdio> #include <cmath> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <map> #include <set> #include <vector> #include <iostream> using namespace std; #define ptf(ar1,ar2) pr__ll64f("%I64d:%I64d\n",ar1,ar2); typedef __int64 ll; const ll maxn = 131707+500; int tm[1000005]; ll pre[1000005]; ll back[1000005]; ll temp1[1000005]; ll min(ll a,ll b) {return a<b?a:b;} ll ok=0; int prim[10005]; void ff(int x) { int ret; for (int i=2; i*i<=x; i++) { if (x%i==0) { prim[++ok]=i; while(x%i==0) x=x/i; } } if (x!=1) prim[++ok]=x; } int main() { int n,a,b; ll i,j; cin>>n>>a>>b; for (i=1; i<=n; i++) scanf("%d",&tm[i]); for (i=-1;i<=1;i++) //求质因数 ff(tm[1]+i),ff(tm[n]+i); sort(prim+1,prim+1+ok); ok=unique(prim+1,prim+1+ok)-prim-1; //去重 ll minn=9223372036854775807; for (ll k=1; k<=ok; k++) //枚举最终以第k个质因数为GCD { for (i=1;i<=n;i++) //求pre[],表示从1到i遇到不合法的数全都change掉的代价 { if (tm[i]%prim[k]==0) pre[i]=pre[i-1]; else if ((tm[i]+1)%prim[k]==0||(tm[i]-1)%prim[k]==0) pre[i]=pre[i-1]+b; else {pre[i]=1e16; } //表示从当前i开始后面的不合法的数都不可change要remove } for (i=n;i>=1;i--) //求back[],表示从i到n遇到不合法的数全都change掉的代价 { if (tm[i]%prim[k]==0) back[i]=back[i+1]; else if ((tm[i]+1)%prim[k]==0||(tm[i]-1)%prim[k]==0) back[i]=back[i+1]+b; else {back[i]=1e16;break ;} //表示从当前i开始前面的数都不可change要remove } temp1[0]=1e16; for (i=1;i<=n+1;i++) //预处理temp[i]表示,对于固定的j,从1到i选一个i使得ans最小的i temp1[i]=min(temp1[i-1],pre[i-1]+(1-i)*a); for (i=n+1;i>=1&&back[i]!=1e16;i--) //枚举j minn=min(minn,temp1[i]+back[i]+a*(i-1)); } printf("%I64d\n",minn); return 0; }
