|
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
|
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int map[100001][3];
int n;
int dy[3] = { -1,0,1 };
int min_res = 987654321, max_res = 0;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) {
cin >> map[i][j];
}
}
int max_dp[2][3] = {{0}}, min_dp[2][3] = {{0}};
max_dp[0][0] = min_dp[0][0] = map[0][0];
max_dp[0][1] = min_dp[0][1] = map[0][1];
max_dp[0][2] = min_dp[0][2] = map[0][2];
for (int i = 1; i < n; i++) {
max_dp[i%2][0] = max(max_dp[(i-1)%2][0], max_dp[(i-1)%2][1]) + map[i][0];
max_dp[i%2][1] = max(max_dp[(i-1)%2][0], max(max_dp[(i-1)%2][1],max_dp[(i-1)%2][2])) + map[i][1];
max_dp[i%2][2] = max(max_dp[(i-1)%2][1], max_dp[(i-1)%2][2]) + map[i][2];
min_dp[i%2][0] = min(min_dp[(i-1)%2][0], min_dp[(i-1)%2][1]) + map[i][0];
min_dp[i%2][1] = min(min_dp[(i-1)%2][0], min(min_dp[(i-1)%2][1],min_dp[(i-1)%2][2])) + map[i][1];
min_dp[i%2][2] = min(min_dp[(i-1)%2][1], min_dp[(i-1)%2][2]) + map[i][2];
// cout << "debug " << dp[i%2][0] << " " << dp[i%2][1] << " " << dp[i%2][2] << '\n';
}
cout << max(max_dp[(n-1)%2][0], max(max_dp[(n-1)%2][1], max_dp[(n-1)%2][2])) << ' ';
cout << min(min_dp[(n-1)%2][0], min(min_dp[(n-1)%2][1], min_dp[(n-1)%2][2])) << '\n';
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
BOJ/C++