백준 1657 - 두부장수 장홍준

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

 

현재 위치에서 뒤의 몇 열을 비트 마스크로 관리하는 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, m;
string ar[14];
int dp[14][14][1 << 15];
int score[140][140];
 
int memo(int r, int c, int mask)
{
  if (c == m) return memo(r + 1, 0, mask);
  if (r * m + (1 + c) >= n * m) return 0;
  int &ret = dp[r][c][mask];
 
  if (ret != -1) return ret;
  ret = 0;
 
  if (mask & 1) return ret = memo(r, c + 1, mask >> 1);
 
  int tmp = memo(r, c + 1, mask >> 1);
 
  if (c < m - 1 and (mask & 2) == 0)
  {
    int val = score[ar[r][c]][ar[r][c + 1]];
    tmp = max(tmp, val + memo(r, c + 2, mask >> 2));
  }
 
  if (r < n - 1 and (mask & (1 << m)) == 0)
  {
    int val = score[ar[r][c]][ar[r + 1][c]];
    int n_mask = mask | (1 << m);
    tmp = max(tmp, val + memo(r, c + 1, n_mask >> 1));
  }
 
  return ret += tmp;
}
 
void solve()
{
  score['A']['A'] = 10;
  score['A']['B'] = 8;
  score['A']['C'] = 7;
  score['A']['D'] = 5;
  score['A']['F'] = 1;
  score['B']['A'] = 8;
  score['B']['B'] = 6;
  score['B']['C'] = 4;
  score['B']['D'] = 3;
  score['B']['F'] = 1;
  score['C']['A'] = 7;
  score['C']['B'] = 4;
  score['C']['C'] = 3;
  score['C']['D'] = 2;
  score['C']['F'] = 1;
  score['D']['A'] = 5;
  score['D']['B'] = 3;
  score['D']['C'] = 2;
  score['D']['D'] = 2;
  score['D']['F'] = 1;
  score['F']['A'] = 1;
  score['F']['B'] = 1;
  score['F']['C'] = 1;
  score['F']['D'] = 1;
 
  memset(dp, -1, sizeof dp);
  cin >> n >> m;
  for (int i = 0; i < n; i++)
  {
    cin >> ar[i];
  }
 
  cout << memo(0, 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();
}

제출 기록