728x90
https://www.acmicpc.net/problem/23280
다음 점화식을 정의하자.
$dp(i, j, k) := $ $i$번째 순서에서 왼손이 $j$, 오른손이 $k$에 있을 때 최적해
번호는 총 12개가 있으므로 약 10001 × 12 × 12 크기의 메모리를 사용하여 동적 계획법을 시행할 수 있다.
처음에 왼손과 오른손이 각각 번호 1, 3에 있다고 했으므로 $dp(0, 0, 2)$부터 메모이제이션을 하여 정답을 계산할 수 있다.
정답 코드 - C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#pragma GCC target("fma,avx,avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
using namespace std;
using ll = int_fast64_t;
using pii = pair<int, int>;
int n, a, b;
int dp[10001][13][13];
int ar[10001];
inline int finger(int go, int to)
{
--go, --to;
int cr = go / 3;
int cc = go % 3;
int nr = to / 3;
int nc = to % 3;
return abs(cr - nr) + abs(cc - nc);
}
int memo(int here, int l, int r)
{
if (here >= n) return 0;
auto &ret = dp[here][l][r];
if (ret != -1) return ret;
ret = 0;
int tmp = 2e9;
int nxt_l = finger(l, ar[here + 1]) + a;
int nxt_r = finger(r, ar[here + 1]) + b;
tmp = min(tmp, memo(here + 1, ar[here + 1], r) + nxt_l);
tmp = min(tmp, memo(here + 1, l, ar[here + 1]) + nxt_r);
return ret = tmp;
}
void solve()
{
cin >> n >> a >> b;
for (int i = 1; i <= n; i++)
{
cin >> ar[i];
}
memset(dp, -1, sizeof dp);
cout << memo(0, 1, 3);
}
int main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin.tie(nullptr);
ios::sync_with_stdio(false);
solve();
}
|
cs |
728x90
'백준 > DP' 카테고리의 다른 글
[USACO] 백준 5945 - Treasure Chest (1) | 2024.11.20 |
---|---|
백준 12199 - Password Attacker (Large) (1) | 2024.11.19 |
백준 32250 - Super Shy (Easy) (0) | 2024.11.11 |
백준 1398 - 동전 문제 (1) | 2024.04.25 |
백준 2040 - 수 게임 (3) | 2022.09.28 |