Bitonic Tour DP
Bitonic Tour 는 계산 기하학에서 다음과 같이 설명된다.
점들을 한 개씩 거쳐가며 시작점을 제외한 방문한 점은 다시 방문안하는 싸이클
이것이 PS에 흔히 이용되는 방법은 DP이다.
위와 같은 성질 그대로 시작점에서 다른 도착점을 찍고 다시 시작점까지 돌아오는데, 시작점을 제외한 점들은 다시 방문하지 않고 돌아오는 방법과 관련된 연산들이 요구된다.
이러한 문제를 해결하는 주된 방법은, 갔다 돌아오는 방식을 사용하지 않고,
시작점에서 도착점까지 처음부터 두 개의 경로를 관리하며 도착점에 둘 다 도달시키는 방법을 고려하는 것이다.
성질
Bitonic Tour DP임을 추측할 수 있는 몇 가지 성질들이 있다.
응용문제
다음과 같은 문제를 살펴보자.
BOJ 10272 - 현상금 사냥꾼 김정은
BOJ 10272 - 현상금 사냥꾼 김정은
$x$의 좌표는 모두 다르며 시작점에서 가장 오른쪽 점을 찍고 다시 돌아오는데, 최소한의 거리로 방문을 해야한다고 한다.
게다가 방문되는 순서는 항상 진행 방향으로 $x$가 일정하게 증가하거나 감소한다고 하고, 모든 행성을 방문해야 한다고 한다.
$dp$를 다음과 같이 정의하자.
$dp[a][b]=$현재 $s \to e$로 가는 경로에선 $a$ 에 있고, $e \to s$로 가는 경로에선 $b$에 있을 때 최소 경로 길이
행성들이 $x$좌표에 대해 오름차순으로 $p_1, p_2, p_3, \dots, p_n$ 라고 하자. $(s=p_1,~~e=p_n)$
현재 위치가 $(a, b)$ 일 때, 일반성을 잃지않고 $a<b$라 하자.
점화식은 $dp[a][b]=\mathrm{Min} \left( dp[b+1][b] + dist(a, b+1), dp[a][b+1] + dist(b, b+1) \right)$
$b=n$ 이라면 예외적으로 $dist(a,n)$을 더해주고 종료한다.
$p_a < p_c < p_b$ 인 $c$중 방문되지 않은 점이 귀납적으로 존재할 수 없기때문에 항상 $b+1$ 인 지점만 고려해주면 된다.
$p_c$는 항상 현재 $p_b$에 있는 점의 경로에 포함이 되어있을 것이기 때문이다.
코드는 다음과 같다.
void solve() {
int n;
cin >> n;
vector<pd> a(n);
for (auto &[x, y]: a) cin >> x >> y;
vector<vector<double>> dp(n, vector<double>(n, -1));
function<double(int, int)> fn = [&](int i, int j) -> double {
if (i > j) swap(i, j);
if (i == n - 1 && j == n - 1) return 0;
if (j == n - 1) return dist(a[i], a[n - 1]);
double &ret = dp[i][j];
if (ret > -0.5) return ret;
return ret = min(fn(j + 1, j) + dist(a[i], a[j + 1]),
fn(i, j + 1) + dist(a[j], a[j + 1]));
};
cout << setprecision(15) << fixed << fn(0, 0) << endl;
}
BOJ 2507 - 공주 구하기
BOJ 2507 - 공주 구하기
이 문제는 비슷한데 좀더 조건이 까다롭다.
하지만 바이토닉 투어인것을 짐작할 수 있는 힌트들은 있다.
1. 시작점을 제외하고 한번 방문한 지점을 다시 방문하지 않는다.
2. 제일 멀리 떨어져있는 지점을 방문하고 다시 시작점으로 돌아온다.
3. 투어를 진행할 때 한 방향으로만 이동한다.
근데 이 문제는 모든 점을 밟을 필요가 없고, 경우의 수를 구하는 문제이므로
어떤 $(a, b)$ 상태에서 $a$ 에서 $N$ 방향으로 진행할 때 밟을 수 있는 정점들이 어디어디인가와
$N$ 에서 다시 돌아올 때 $b$로 올 수 있는 정점들이 어디어디인가를 미리 저장해두면 편하다.
또한 돌아올땐 공주와 함께 오므로 또 가능한 섬이 제한되므로 이것에 유의한다.
동일하게 2차원 dp로
$dp[a][b] = (a, b)$ 상태일 때 경우의 수 라고 하자.
$dp[N][N] = 1$ 이 된다.
이제 $a$ 에서 $N$ 방향으로 갈 수 있는 점 중, $b$ 보다 큰 곳에 위치한 점들로 모두 이동한 경우의 수를 더한다.
마찬가지로 $N$ 에서 $b$ 방향으로 올 수 있는 점 중, $a$ 보다 큰 곳에 위치한 점들로 모두 이동한 수를 더한다.
즉, 위 문제와 동일하게 $max(a + b)$ 보다 큰 정점들만 사용한 것이다.
$(a, b)$ 에서 $(c, b)$ 로 넘어간 시점에서 우린 $a + 1 \sim c - 1$ 의 정점들을 사용하지 않는 경우의 수를 세주는 것이기 때문에 그곳에 있는 정점은 skip 해주는게 맞다.
그런데 우리가 구하는게 경우의 수라는 것에 유의하자.
$c, d$ 라는 섬이 있을 때 $(a, b) \to (c, b)$ 로 간 경우나 $(a, b) \to (a, d)$ 로 간 경우나 결국 싸이클이 형성되면 동일한 경로이기 때문에 2를 나누어주어야 한다.
근데 모듈러 연산때문에 $2$를 나누어주기 애매하므로 $b$로 오는 점들 중 $N$ 에서 오는것은 세지 않는 트릭으로 이 문제를 해결할 수 있다! 이건 약간 맞나 의아했는데 proof by ac가 되었다.
const int mod = 1e3;
void solve() {
int n;
cin >> n;
vector<array<int, 3>> arr(n);
for (auto&[x, s, p]: arr) cin >> x >> s >> p;
vvi jump(n), jump_princess(n);
for (int i = 0; i < n; i++) {
for (int j = n - 1; j > i; j--) {
int dist = arr[j][0] - arr[i][0];
if (dist <= arr[i][1])
jump[i].pb(j);
if (arr[j][2] && (arr[i][2] || i == 0) && dist <= arr[j][1])
jump_princess[i].pb(j);
}
}
vvi dp(n, vi(n, -1));
function<int(int, int)> fn = [&](int i, int j) -> int {
if (i == n - 1 && j == n - 1) return 1;
int &ret = dp[i][j];
if (~ret) return ret;
ret = 0;
for (int nxt: jump[i]) {
if (nxt != n - 1 && nxt <= j) break;
ret += fn(nxt, j);
if (ret >= mod) ret -= mod;
}
for (int nxt: jump_princess[j]) {
if (nxt <= i) break;
ret += fn(i, nxt);
if (ret >= mod) ret -= mod;
}
return ret;
};
cout << fn(0, 0);
}
BOJ 8890 - Critical 3-Path
BOJ 8890 - Critical 3-Path
Bitonic tour가 아닌 세갈래로 나아가야 한다.
이걸 반복문 DP로 구성해서 중복된 정점을 거치지 않게 DP를 돌리는 방법도 있는 모양이지만, 위상 정렬을 써서 각 정점마다 Rank를 메긴뒤에 가장 Rank가 작은 정점부터 이동시켜주는 방식이 직관적인 것 같다.
$dp[a][b][c]=$현재 $(a,b,c)$상태일 때, $(t_1,t_2,t_3)$ 에 도달하는 경로의 최대값
로 두고 풀면 $O(n^4)$가 된다.
void solve() {
int n, m;
cin >> n >> m;
vi S(3), T(3);
fv(S);
fv(T);
vector<vvi> dp(n, vvi(n, vi(n, -1)));
for (int &i: S) i--;
for (int &i: T) i--;
vector<vector<pi>> edges(n);
vi rank(n, -1e9), in(n);
for (int i = 0, u, v, w; i < m; i++) {
cin >> u >> v >> w, u--, v--;
edges[u].pb({v, w});
in[v]++;
}
queue<int> q;
for (int i = 0; i < n; i++) if (!in[i]) q.push(i), rank[i] = 0;
while (sz(q)) {
int cur = q.front();
q.pop();
for (auto &[to, _]: edges[cur]) {
in[to]--;
rank[to] = max(rank[to], rank[cur] + 1);
if (!in[to]) q.push(to);
}
}
debug(rank);
function<int(int, int, int)> fn = [&](int a, int b, int c) -> int {
bool ea = a == T[0];
bool eb = b == T[1];
bool ec = c == T[2];
if (ea && eb && ec) {
return 0;
}
int &ret = dp[a][b][c];
if (~ret) return ret;
ret = -1e9;
int go_a = eb && ec && !ea;
go_a = go_a || eb && rank[a] <= rank[c] && !ea;
go_a = go_a || ec && rank[a] <= rank[b] && !ea;
go_a = go_a || rank[a] <= rank[b] && rank[a] <= rank[c] && !ea;
int go_b = ea && ec && !eb;
go_b = go_b || ea && rank[b] <= rank[c] && !eb;
go_b = go_b || ec && rank[b] <= rank[a] && !eb;
go_b = go_b || rank[b] <= rank[a] && rank[b] <= rank[c] && !eb;
int go_c = ea && eb && !ec;
go_c = go_c || ea && rank[c] <= rank[b] && !ec;
go_c = go_c || eb && rank[c] <= rank[a] && !ec;
go_c = go_c || rank[c] <= rank[a] && rank[c] <= rank[b] && !ec;
if (go_a) {
for (auto &[to, w]: edges[a]) {
if (to == a || to == b || to == c) continue;
ret = max(ret, w + fn(to, b, c));
}
} else if (go_b) {
for (auto &[to, w]: edges[b]) {
if (to == a || to == b || to == c) continue;
ret = max(ret, w + fn(a, to, c));
}
} else if (go_c) {
for (auto &[to, w]: edges[c]) {
if (to == a || to == b || to == c) continue;
ret = max(ret, w + fn(a, b, to));
}
} else {
assert(0);
}
return ret;
};
int ret = fn(S[0], S[1], S[2]);
cout << max(0ll, ret) << endl;
}
Comments