(2315) 가로등 끄기

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

단계별로 풀어보기

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

 

 

 

마징가는 연속적으로 이동하며 불을 끄기 때문에 a~b번 가로등의 불을 껐다면 마징가는 a번 아니면 b번 가로등에 위치해 있다.

DP[a][b][x]를 마징가가 a~b번 가로등을 껐고 x가 0이면 왼쪽, 1이면 오른쪽에 마징가가 있을 때 남은 불을 끄기 위한 최소 비용이라고 하자.

불을 다 끄는 것이 목표이므로 DP[1][n][0]=DP[1][n][1]=0이다.

또한 DP[a][b][x]는 DP[a-1][b][0], DP[a-1][b][1], DP[a][b-1][0], DP[a][b-1][1]과 각각의 경우에 추가로 들어가는 비용을 더한 값 중 최소값이다.

재귀를 이용해 구현하면 우리가 원하는 정답은 DP[m][m][0] (DP[m][m][1]이여도 상관없음)에 저장된다.

 

 

 

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

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;
  
  vector<int> d(n+1), w(n+1), s(n+1);
  vector dp(n+1, vector<vector<int>> (n+1, vector<int> (2, -1)));
  
  for(int i=1;i<=n;i++){
    cin >> d[i] >> w[i];
    s[i]= s[i-1]+w[i];
  }
  
  dp[1][n][0]= 0;
  dp[1][n][1]= 0;
  
  auto func= [&](auto& self, int l, int r, int dir) -> int {
    if(m<l || r<m)  return INF;
  
    int &ret= dp[l][r][dir];
    
    if(ret>=0)  return ret;
    
    ret= INF;
    
    int cur= (dir==0 ? d[l] : d[r]);
    int waste= s[n]-s[r]+s[l-1];
    
    if(1<l){
      ret= min(ret, self(self, l-1, r, 0) + (cur-d[l-1])*waste);
    }
    if(r<n){
      ret= min(ret, self(self, l, r+1, 1) + (d[r+1]-cur)*waste);
    }
    
    return ret;
  };
  
  cout << func(func, m,m,0);
  
  return 0;
}