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

https://www.acmicpc.net/problem/23280

 

다음 점화식을 정의하자.

$dp(i, j, k) :=$ $i$번째 순서에서 왼손이 $j$, 오른손이 $k$에 있을 때 최적해

번호는 총 12개가 있으므로 약 10001 × 12 × 12 크기의 메모리를 사용하여 동적 계획법을 시행할 수 있다.

처음에 왼손과 오른손이 각각 번호 1, 3에 있다고 했으므로 $dp(0, 0, 2)$부터 메모이제이션을 하여 정답을 계산할 수 있다.

정답 코드 - C++

#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();
}