[KOI] 백준 10937 - 두부 모판 자르기

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

 

현재 위치에서 뒤의 몇 열을 비트 마스크로 관리하는 dp이다. 풀이의 근원은 이 포스트, 또는 이 자료를 참조하라.

 

이 문제는 위와 달리 칸을 선택하지 않는 경우도 있으므로 이를 고려해서 동적 계획법을 수행하면 된다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int n;
string ar[11];
int dp[11 * 11][1 << 12];
int score[140][140];
 
int memo(int idx, int mask)
{
  if (idx >= n * n - 1) return 0;
 
  int &ret = dp[idx][mask];
 
  if (ret != -1) return ret;
  ret = 0;
 
  ret = memo(idx + 1, mask >> 1);
 
  if (mask & 1) return ret = max(ret, memo(idx + 1, mask >> 1));
 
  int val = 0;
 
  if ((mask & 2) == 0 and idx + 1 < n * n)
  {
    val = score[ar[idx / n][idx % n]][ar[idx / n][idx % n + 1]];
    ret = max(ret, val + memo(idx + 2, mask >> 2));
  }
 
  if ((mask & (1 << n)) == 0 and idx + n < n * n)
  {
    val = score[ar[idx / n][idx % n]][ar[idx / n + 1][idx % n]];
    int n_mask = mask | (1 << n);
    ret = max(ret, val + memo(idx + 1, n_mask >> 1));
  }
 
  return ret;
}
 
void solve()
{
  score['A']['A'] = 100;
  score['A']['B'] = score['B']['A'] = 70;
  score['A']['C'] = score['C']['A'] = 40;
  score['B']['B'] = 50;
  score['B']['C'] = score['C']['B'] = 30;
  score['C']['C'] = 20;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> ar[i];
 
  memset(dp, -1, sizeof dp);
  cout << memo(0, 0);
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록