📝 문제 정보#
🧐 관찰 및 접근#
- 얻는 점수가 $M_i - t * p_i$가 아닌 $M_i$라면, 단순한 배낭문제일텐데..
- 이걸 위해서 $N$에 대한 비트마스킹을 추가하는건 미친짓이다
- 그런데, 어떤 문제들을 풀기로 결정했다면, 그 문제들에 대해 순서를 정하는건 그리디하게 되지 않나?
- 문제 $i, j$가 있다고 하자.
- $i \rightarrow j$로 풀면 $(M_i - t * P_i) + (M_j - (t + R_i)*P_j)$ 점을 얻게 되고
- $j -> i$로 풀면 $(M_j - t*P_j) + (M_i - (t + R_j) * P_i)$ 점을 얻게 된다.
- 위에서 아래 식을 빼면 $P_i * R_j - P_j * R_i$ 이고, $i \rightarrow j$가 이득이기 위해선 이게 양수여야하므로
- $\frac{P_i}{R_i} \geq \frac{P_j}{R_j}$로 정렬하는 그리디 전략이 유효하다.
- 그렇다면 이 순서로 냅색 DP를 수행하자.
💻 풀이#
- 코드 (C++):
void solve(){
int N, T; cin >> N >> T;
vector<Problem> Prob(N);
rep(i, 0, N) cin >> Prob[i].M;
rep(i, 0, N) cin >> Prob[i].P;
rep(i, 0, N) cin >> Prob[i].R;
sort(all(Prob), [](Problem &A, Problem &B){
return A.P * B.R > B.P * A.R;
});
vector<ll> DP(T+1);
for(auto [M, P, R]: Prob) rrep(t, 0, T+1){
if(t - R < 0) break;
DP[t] = max(DP[t], DP[t - R] + (M - P*t));
}
ll ans = 0;
rep(i, 0, T+1) ans = max(ans, DP[i]);
cout << ans;
}