Codeforces 623B:Array GCD

B. Array GCD
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given array ai of length n. You may consecutively apply two operations to this array:
remove some subsegment (continuous subsequence) of length m n and pay for it m·a coins;
change some elements of the array by at most 1, and pay b coins for each change.
Please note that each of operations may be applied at most once (and may be not applied at all) so you can remove only one segment and each number may be changed (increased or decreased) by at most 1. Also note, that you are not allowed to delete the whole array.
Your goal is to calculate the minimum number of coins that you need to spend in order to make the greatest common divisor of the elements of the resulting array be greater than 1.
Input
The first line of the input contains integers n, a and b (1 ≤ n ≤ 1 000 000, 0 ≤ a, b ≤ 109) — the length of the array, the cost of removing a single element in the first operation and the cost of changing an element, respectively.
The second line contains n integers ai (2 ≤ ai ≤ 109) — elements of the array.
Output
Print a single number — the minimum cost of changes needed to obtain an array, such that the greatest common divisor of all its elements is greater than 1.
Sample test(s)
input

3 1 4
4 2 3

output

input

5 3 2
5 17 13 5 6

output

input

8 3 4
3 7 5 4 3 12 9 4

output

Note
In the first sample the optimal way is to remove number 3 and pay 1 coin for it.
In the second sample you need to remove a segment [17, 13] and then decrease number 6. The cost of these changes is equal to2·3 + 2 = 8 coins.
하나의 그룹을 지정하면 원소를 삭제하는 대가가 a이고 원소를 삭제하면 연속적인 부분만 삭제할 수 있습니다.원소+1 또는 -1에 대한 대가는 b이다. 이런 조작 후에 모든 원소의 최대 공약수는 2보다 크고 최소 대가를 묻는다.
a1과 an은 틀림없이 잉여가 있을 것이다. 그러므로 a1-1 a1 a1+1 an-1 ananan+1 조작에 대해 질적 인수를 찾고 dp[i][j]로 i번째 원소를 스캔할 때 원소를 삭제하지 않았음을 표시한다. 원소를 삭제하고 있다. 원소를 삭제한 최소 대가.
코드:

#pragma warning(disable:4996)
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include ;
#include 
#include 
using namespace std;
typedef long long ll;

#define INF 0x3fffffffffffffff

const ll mod = 1e9 + 7;
const int maxn = 1000005;

ll n, a, b;
ll cost[maxn],val[maxn], dp[maxn][3];
vectorgcd;

ll cal(ll x)
{
	int i;
	for (i = 1; i <= n; i++)
	{
		cost[i] = 1e12 + 7;
		if (val[i] % x == 0)
		{
			cost[i] = 0;
		}
		else if ((val[i] + 1) % x == 0 || (val[i] - 1) % x == 0)
		{
			cost[i] = b;
		}
	}
	for (i = 1; i <= n; i++)
	{
		dp[i][0] = dp[i - 1][0] + cost[i];
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + a;
		dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + cost[i];
	}
	return min(min(dp[n][2], dp[n][1]), dp[n][0]);
}

void pri(ll x)
{
	int i;
	for (i = 2; i*i <= x; i++)
	{
		if (x % i == 0)
			gcd.push_back(i);
		while (x % i == 0)
			x = x / i;
	}
	if (x != 1)
		gcd.push_back(x);
}

void solve()
{
	int i;
	scanf("%I64d%I64d%I64d", &n, &a, &b);

	for (i = 1; i <= n; i++)
	{
		scanf("%d", &val[i]);
	}
	pri(val[1]);
	pri(val[1] + 1);
	pri(val[1] - 1);
	pri(val[n]);
	pri(val[n] + 1);
	pri(val[n] - 1);
	sort(gcd.begin(), gcd.end());
	gcd.erase(unique(gcd.begin(), gcd.end()), gcd.end());
	ll ans = INF, sz = gcd.size();
	for (i = 0; i < sz; i++)
	{
		ans = min(ans, cal(gcd[i]));
	}
	cout << ans << endl;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("i.txt", "r", stdin);
	freopen("o.txt", "w", stdout);
#endif
	
	solve();

	return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Codeforces 1287C Garland

제목 링크:Codeforces 1287C Garland 사고방식: 우리기dp[i][j][0]와 dp[i][j][1]는 각각 i개가 홀수/짝수이고 앞의 i개 안에 j개의 짝수가 있는 상황에서 i개의 최소 복잡도.첫 번...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Codeforces 623B:Array GCD

좋은 웹페이지 즐겨찾기