(13448) SW 역량 테스트

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

단계별로 풀어보기

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

 

 

 

그리디 알고리즘에서 썼던 Exchange argument 기법을 쓸 수 있다.

i번, j번 문제가 있고 연속해서 푸는 경우를 생각하자.

1) i번을 먼저 풀면 얻는 점수는 Mi-Ri*Pi, 다음으로 j번을 풀면 얻는 점수는 Mj-(Ri+Rj)*Pi

2) j번을 먼저 풀면 얻는 점수는 Mj-Rj*pj, 다음으로 i번을 풀면 얻는 점수는 Mi-(Ri+Rj)*Pj

같은 값은 비교 의미가 없으므로 빼주면 1번 경우에는 -Rj*Pi점을 얻고 2번 경우에는 -Ri*Pj점을 얻는다.

두 문제를 푸는 시간은 같으므로 이전 문제나 이후 문제 점수에 영향을 주지 않으며,

-Ri*Pj<-Rj*Pi라면 i번 문제를 j번 문제보다 먼저 푸는 것이 유리하다. 이 조건으로 문제를 정렬하면 된다.

다만 이 문제에는 제한 시간 T가 있으므로 정렬이 끝난 후 해당 순서로 문제를 탐색하며 푸는 경우와 안 풀고 넘어가는 경우 중 최대값을 찾아 DP값을 갱신해야 한다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct problem{
  long m;
  long p;
  long r;
};

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, t;
  
  cin >> n >> t;
  
  vector<problem> v(n);
  vector dp(n, vector<long> (t+1, -1));
  
  for(int i=0;i<n;i++)  cin >> v[i].m;
  for(int i=0;i<n;i++)  cin >> v[i].p;
  for(int i=0;i<n;i++)  cin >> v[i].r;
  
  sort(v.begin(), v.end(), [](problem& A, problem& B){
    return A.r*B.p < A.p*B.r;
  });
  
  auto solve= [&](auto &self, int now, long nowt) -> long{
    if(now>=n)  return 0L;
    
    long &ret= dp[now][nowt];
    
    if(ret>=0)  return ret;
    
    ret= 0;
    
    ret= max(ret, self(self, now+1, nowt));
    
    if(nowt+v[now].r<=t){
      ret= max(ret, self(self, now+1, nowt+v[now].r) + v[now].m-(nowt+v[now].r)*v[now].p);
    }
    
    return ret;
  };
  
  cout << solve(solve, 0, 0);
  
  return 0;
}