(DP - 최적의 순서로 맞추기) 13448 SW 역량 테스트

13448 SW 역량 테스트 https://www.acmicpc.net/problem/13448
Codeforces #436 (Div.2) E - Fire http://codeforces.com/contest/864/problem/E

dp는 최적 부분구조를 이뤄야 시행될 수 있다.
만약 주어지는 입력값이 작으면 bitmask dp나 set 또는 map에 저장시켜 풀 수 있지만
그 값이 크면 대부분 TLE가 발생한다.
그러므로 최적 부분구조를 만드는것이 중요하다.

1. SW 역량 테스트
T분 동안 진행되는 시험에 N개의 문제가 나온다.
$i$번 문제를 $t$분만에 풀면 $M_{i}-t*P_{i}$점을 얻게된다.
$i$번 문제 푸는 시간은 $R_{i}$이다.
얻을 수 있는 점수의 최댓값을 구하는 문제다.

얼마전에 삼성 SW역량 테스트 A형을 봤는데 생각나게끔 하는 문제다.
사람이 생각보다 많이 왔고 A형이라 매우 쉽게 나왔다.

어쨌든 문제로 돌아가면 주어진 문제들의 정보를 입력 그대로 푼다면 위에서 언급한
bitmask dp나 set정도를 사용해야한다. (하지만 TLE)

따라서 어떻게든 정렬을 해야하는데 수식을 전개하면 아주 놀라운 일이 벌어진다.
https://www.acmicpc.net/board/view/11824
(수식 전개는 별로어렵지 않으니 직접해보는것 추천)

요약 : $R_{i}/P_{i} < R_{j}/P_{j}$ 이면 $i$를 푼 후 $j$를 푸는것이 낫다.
따라서 정렬한 후에 dp로 풀면된다.

#include <cstdio> #include <algorithm> #include <vector> #include <cstring> using namespace std; struct Save {      long long M, P, R;      double pivot; }; int N, T; Save save[51]; long long dp[51][100001]; long long solve(int idx, long long time) {     if (idx == N) return 0;     long long &ret = dp[idx][time];     if (ret != -1) return ret;     ret = 0;     if (idx + 1 <= N && time + save[idx].R <= T)         ret = max(ret, solve(idx + 1, time + save[idx].R) + save[idx].M - (time + save[idx].R)*save[idx].P);     if (idx + 1 <= N)         ret = max(ret, solve(idx + 1, time));     return ret; } int main() {     memset(dp, -1, sizeof dp);     scanf("%d%d", &N, &T);     for (int n = 0;n < N;n++) scanf("%lld", &save[n].M);     for (int n = 0;n < N;n++) scanf("%lld", &save[n].P);     for (int n = 0;n < N;n++) scanf("%lld", &save[n].R);     for (int n = 0;n < N;n++) save[n].pivot = save[n].R / (double)save[n].P;     sort(save, save + N, [](Save const &a, Save const &b)->bool {         return a.pivot < b.pivot;     });     printf("%lld\n", solve(0, 0));     return 0; } Colored by Color Scripter

cs

2. Codeforces #436 (Div.2) E - Fire
집에 불이 났다.
집에는 값어치가 매겨진 물품들이 있고 그 물품 $i$를 구출하는데 
걸리는 시간 $t_{i}$, 다 타버리는 시간 $d_{i}$, 물품의 가치 $p_{i}$가 주어진다.
구조할 수 있는 물품의 가치의 합을 최대화하도록 만들고 어떤 물품을 구조했는지 구하는 문제다.

이 문제도 최적 부분구조를 만들어야한다.
바로 $d_{i}$를 최소화 하는것부터 구출하면 최적 부분구조를 이룰 수 있다.

#include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <map> using namespace std; #define mp(a,b) make_pair(a,b) #define mt(a,b,c) mp(a,mp(b,c)) #define mf(a,b,c,d) mp(mp(a,b),mp(c,d)) typedef long long ll; struct Save {     int t, d, p;     int idx; }; int N; Save arr[101]; vector<int> ans; int dp[101][2002]; int solve(int idx, int time) {     if (idx >= N) return dp[idx][time] = 0;     int &ret = dp[idx][time];     if (ret != -1) return ret;     ret = 0;     if (time + arr[idx].t < arr[idx].d) {         ret = max(ret, solve(idx + 1, time + arr[idx].t) + arr[idx].p);     }     ret = max(ret, solve(idx + 1, time));     return ret; } void reconstruct(int idx, int time) {     if (idx >= N) return;     int here = dp[idx][time];     if (time + arr[idx].t < arr[idx].d && here == dp[idx + 1][time + arr[idx].t] + arr[idx].p) {         ans.push_back(idx);         reconstruct(idx + 1, time + arr[idx].t);         return;     }     reconstruct(idx + 1, time); } int main() {     memset(dp, -1, sizeof dp);     scanf("%d", &N);     for (int n = 0;n < N;n++) scanf("%d%d%d", &arr[n].t, &arr[n].d, &arr[n].p), arr[n].idx = n;     sort(arr, arr + N, [](Save &a, Save &b)->bool {         return a.d == b.d ? a.t < b.t : a.d < b.d;     });     printf("%d\n", solve(0, 0));     reconstruct(0, 0);     printf("%d\n", ans.size());     for (int &next : ans)printf("%d ", arr[next].idx + 1);     return 0; } Colored by Color Scripter

cs