(1657) 두부장수 장홍준

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

단계별로 풀어보기

50단계(동적 계획법 4) 7번째

 

 

 

브로큰 프로파일 DP를 이용해 풀면 된다. 어떤 칸에서 다음 단계로 나아가는 경우의 수는 이번 칸 무시, 가능하다면 가로로 자르기와 세로로 자르기 3가지가 있고 가로로 자를 때와 세로로 자를 땐 잘린 두부의 금액만큼 더해주면 된다. 이제 세 경우 중 최대값을 구하면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
#define INF 1000

int main() {
  int n, m, ans= 0;

  cin >> n >> m;
  
  vector<vector<int>> cost={{10,8,7,5,1},{8,6,4,3,1},{7,4,3,2,1},{5,3,2,2,1},{1,1,1,1,0}};
  vector dp(n*m, vector<int> (1<<m, -1)), v(n, vector<int> (m));
  
  for(int i=0;i<n;i++){
    string s;

    cin >> s;

    for(int j=0;j<m;j++){
      if(s[j]=='A')  v[i][j]= 0;
      else if(s[j]=='B')  v[i][j]= 1;
      else if(s[j]=='C')  v[i][j]= 2;
      else if(s[j]=='D')  v[i][j]= 3;
      else  v[i][j]= 4;
    }
  }

  auto func= [&](auto self, int now, int state) -> int {
    if(now==n*m && !state)  return 0;
    if(now>=n*m)  return -INF;
    
    int& ret= dp[now][state];
    
    if(ret!=-1)  return ret;
    
    int x= now/m, y= now%m;
    
    ret= 0;
    
    ret= max(ret, self(self, now+1, state>>1));
    
    if(!(state&1)){
      if(x!=n-1){
        ret= max(ret, cost[v[x][y]][v[x+1][y]]+self(self, now+1, (state>>1)|(1<<(m-1))));
      }
      if(y!=m-1 && !(state&2)){
        ret= max(ret, cost[v[x][y]][v[x][y+1]]+self(self, now+2, (state>>2)));
      }
    }
    
    return ret;
  };
  
  cout << func(func, 0, 0);
  
  return 0;
}