14863 서울에서 경산까지
알고리즘 (dp)
1
2
3
1. dp를 평범하게 진행. dp배열은 dp[101][100001] 로 앞에는 현재 위치, 뒤에는 시간
2. 시간이 맞으면 진행하되, 안맞으면 result 를 초기화해둔 -20000000이 그대로 있음.
3. 0보다 낮으면, 현재 시간포함 0초까지 -20000000로 초기화. 같은 상태에 더 낮은 시간을 가지고 접근하는 걸 막음.
다른 방법 (dp)
1
2
3
4
5
6
1. dp[100005] 로 시간만으로 dp를 만듬.
2. 첫번째 노드의 시간과 값으로 dp 초기화
3. dp 배열을 t=k 부터 검사하여 값이 있으면, dp[j + a] = max(dp[j+a], dp[j] + b) 로 시간을 올려가며 dp를 수행
4. 이때 노드는 앞에서부터 검사한다.
5. 값이 있으면 작업을 수행하고, 끝나면 dp[j] = 0 으로 다시 초기화.
6. 다 끝나면, 저장된 값중 최고값 뽑아서 리턴
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
using namespace std;
int road[101][4], k, n, dp[101][100001], dp2[100001];
//방법 1
int getMaxDP(int cur, int t);
//방법 2
int getMaxDP2();
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> road[i][0] >> road[i][1] >> road[i][2] >> road[i][3];
}
cout << getMaxDP2();
}
int getMaxDP(int cur, int t) {
if (cur == n)
return 0;
if (dp[cur][t] != 0)
return dp[cur][t];
int result = -2000000000;
if (t - road[cur][0] >= 0)
result = getMaxDP(cur + 1, t - road[cur][0]) + road[cur][1];
if (t - road[cur][2] >= 0)
result = max(result, getMaxDP(cur + 1, t - road[cur][2]) + road[cur][3]);
if (result <= 0) {
for (int i = t; i >= 0; i--) {
if (dp[cur][i] < 0)
break;
else
dp[cur][i] = result;
}
}
return dp[cur][t] = result;
}
int getMaxDP2() {
dp2[road[0][0]] = road[0][1];
dp2[road[0][2]] = road[0][3];
for (int i = 1; i < n; i++) {
for (int j = k; j >= 0; j--) {
if (dp2[j] > 0) {
if (j + road[i][0] <= k)
dp2[j + road[i][0]] = max(dp2[j + road[i][0]], dp2[j] + road[i][1]);
if (j + road[i][2] <= k)
dp2[j + road[i][2]] = max(dp2[j + road[i][2]], dp2[j] + road[i][3]);
dp2[j] = 0;
}
}
}
int result = 0;
for (int i = 0; i <= k; i++) {
result = max(result, dp2[i]);
}
return result;
}