BOJ 20367 - 3 Slot Matching

BOJ 20367 - 3 Slot Matching

2개는 계속 들고다닐 수 없다.

그 다음턴에 무조건 두 개중 하나와 결합해야 한다.

$dp[i][j] = i$ 번째 막대를 볼 때 저장된 막대가 $j$ 일 때 최댓값

라고 정의하고 간단히 DP를 정의할 수 있다.

void solve() {
   int n;
   cin >> n;
   vi a(n + 1);
   fv1(a);
   vvi dp(n + 5, vi(n + 5, -1));
   function<int(int, int)> fn = [&](int i, int j) -> int {
      if (i > n) return 0;
      int &ret = dp[i][j];
      if (~ret) return ret;
      ret = 0;

      if (j == 0) {
         ret = fn(i + 1, i);
      } else {
         // 이전것과 이것을 결합할 때
         maxa(ret, fn(i + 1, 0) + a[j] * a[i]);
         if (i != n) {
            maxa(ret, fn(i + 2, j) + a[i] * a[i + 1]);
            maxa(ret, fn(i + 2, i) + a[j] * a[i + 1]);
         }
      }

      return ret;
   };
   cout << fn(1, 0);
}