AIM Tech Round (Div. 2) D. Array GCD(dp)
15101 단어 dp
N≤106의 시퀀스를 지정하고 현재 2가지 조작이 있습니다.0≤M
분석:
삭제된 것은 연속 서열이고 삭제할 수 없기 때문에 a1, an은 적어도 하나를 남길 것이다. gcd가 109개가 많기 때문이다. 그러나 최종 gcd는 a1, a1±1 또는 an, an±1의 소인자인 소인자가 적고 로그급이기 때문에 그 다음에 f[prime][i][3]:=1∼i개수, gcd는 prime, 삭제된 연속 서열→0/가 시작되지 않고 1/삭제 중, 2/삭제가 끝났다.최소한의 대가를 치르고 폭력으로 이동하면 ans=min{f[prime][N][0], f[prime][N][2]} 시간 복잡도 O(nlog109) 주의. dp는 전체 서열을 삭제하지만 생각해보니 이것이 최선이 되지 않을 것이다. 왜냐하면 우리는 최소한 한 수를 남긴 더 좋은 해가 있을 수 있기 때문이다.
코드:
//
// Created by TaoSama on 2016-02-05
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e6 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, A, B;
int a[N];
long long f[2][3]; //0->removed array, not started, 1->removing, 2->finished
inline void getMin(long long &x, long long y) {
if(x > y) x = y;
}
int getCost(int i, int p) {
if(a[i] % p == 0) return 0;
else if((a[i] + 1) % p == 0 || (a[i] - 1) % p == 0) return B;
return INF;
}
void see(int i, int s) {
for(int j = 0; j < 3; ++j)
printf("f[%d][%d]=%I64d
", i, j, f[s][j]);
}
long long gao(int p) {
int s = 0;
memset(f[s], 0, sizeof f[s]);
for(int i = 1; i <= n; ++i) {
memset(f[!s], 0x3f, sizeof f[!s]);
int cost = getCost(i, p);
if(cost != INF) {
getMin(f[!s][0], f[s][0] + cost);
getMin(f[!s][2], f[s][2] + cost);
}
getMin(f[!s][1], f[s][0] + A); //start removing
getMin(f[!s][1], f[s][1] + A); //removing
getMin(f[!s][2], f[s][0] + A); //finish right away
getMin(f[!s][2], f[s][1] + A); //finish removing
s = !s;
// if(p == 2) see(i, s);
}
return min(f[s][0], f[s][2]);
}
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
while(scanf("%d%d%d", &n, &A, &B) == 3) {
for(int i = 1; i <= n; ++i) scanf("%d", a + i);
int leave[] = {a[1], a[n]};
long long ans = 1e18;
for(int i = 0; i < 2; ++i) {
for(int d = -1; d <= 1; ++d) {
int x = leave[i] + d;
for(int j = 2; j * j <= x; ++j) {
if(x % j == 0) {
ans = min(ans, gao(j));
while(x % j == 0) x /= j;
}
}
if(x > 1) ans = min(ans, gao(x));
}
}
printf("%I64d
", ans);
// return 0;
}
return 0;
}물론prefix,suffix를 통해 이 문제를 풀 수 있다.
코드:
//
// Created by TaoSama on 2016-02-05
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e6 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, A, B;
int a[N];
long long f[N], g[N];
long long gao(int p) {
int pos = -1;
for(int i = 1; i <= n; ++i) {
if(a[i] % p == 0) g[i] = g[i - 1];
else if((a[i] + 1) % p == 0 || (a[i] - 1) % p == 0)
g[i] = g[i - 1] + B;
else break;
pos = i;
}
for(int i = 1; i <= n; ++i) {
f[i] = f[i - 1] + A;
if(i <= pos) f[i] = min(f[i], g[i]);
}
g[n + 1] = 0;
long long ret = f[n];
for(int i = n; i; --i) {
if(a[i] % p == 0) g[i] = g[i + 1];
else if((a[i] + 1) % p == 0 || (a[i] - 1) % p == 0)
g[i] = g[i + 1] + B;
else break;
ret = min(ret, f[i - 1] + g[i]);
}
return ret;
}
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
while(scanf("%d%d%d", &n, &A, &B) == 3) {
for(int i = 1; i <= n; ++i) scanf("%d", a + i);
int leave[] = {a[1], a[n]};
long long ans = 1e18;
for(int i = 0; i < 2; ++i) {
for(int d = -1; d <= 1; ++d) {
int x = leave[i] + d;
for(int j = 2; j * j <= x; ++j) {
if(x % j == 0) {
ans = min(ans, gao(j));
while(x % j == 0) x /= j;
}
}
if(x > 1) ans = min(ans, gao(x));
}
}
printf("%I64d
", ans);
}
return 0;
}좋은 웹페이지 즐겨찾기
