본문 바로가기

백준/DP

백준 23280 - 엔토피아의 기억 강화

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<intint>;
 
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 != -1return 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, -1sizeof dp);
  cout << memo(013);
}
 
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