Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // by 100daysofcode #1
- #include <iostream>
- using namespace std;
- // (2579) Climbing stair
- /*
- Max score
- d[n] : n개의 계단의 최대 score
- 1) d[n-1] + a[n];
- 2)
- (stk) 1단계는 생각할 수 있어도,
- 예를 들어 d[n-1]쪽을 생각하면 이
- ----------------------
- (aha) after 포도주 다시 보고, 동영상 그림 이해.
- (stk2) 그래도 이해안가는 부분이 있는데...(밑에 해보니깐 이해됨)
- d[i][1] => Max(d[i-2][1], d[i-2][2]) + a[i]
- => d[i-1][] <== 아하.. 해보니깐 1번 연속, 2번 역속을 넣을 수가 없구나,,
- d[i][2] =>= d[i-1][1] + a[i]
- d[1][1] = a[i];
- d[1][2] = 0;
- */
- long d[301][3];
- int a[301];
- long Max(long a, long b) {
- return a > b ? a : b;
- }
- long go(int i, int j) {
- if (i == 0) return 0; //(wik) later I found
- if (i == 1) {
- if (j == 1) return a[i];
- if (j == 2) return 0;
- }
- if (d[i][j] > 0) return d[i][j];
- long max = 0;
- if (j == 1) {
- max = Max(go(i - 2, 1), go(i - 2, 2)) + a[i];
- }
- if (j == 2) {
- max = go(i - 1, 1) + a[i];
- }
- d[i][j] = max;
- return d[i][j];
- }
- int main() {
- //freopen("input.txt", "r", stdin);
- int n;
- cin >> n;
- for (int i = 1; i <= n; i++) {
- cin >> a[i];
- }
- long max = 0;
- long temp = go(n, 1);
- if (temp > max) max = temp;
- temp = go(n, 2);
- if (temp > max) max = temp;
- cout << max << endl;
- return 0;
- }
Add Comment
Please, Sign In to add comment