Guest User

Untitled

a guest
Jan 16th, 2019
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.31 KB | None | 0 0
  1. // by 100daysofcode #1
  2.  
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. // (2579) Climbing stair
  7.  
  8. /*
  9.  
  10. Max score
  11.  
  12. d[n] : n개의 계단의 최대 score
  13.  
  14. 1) d[n-1] + a[n];
  15. 2)
  16.  
  17.  
  18. (stk) 1단계는 생각할 수 있어도,
  19. 예를 들어 d[n-1]쪽을 생각하면 이
  20. ----------------------
  21. (aha) after 포도주 다시 보고, 동영상 그림 이해.
  22. (stk2) 그래도 이해안가는 부분이 있는데...(밑에 해보니깐 이해됨)
  23.  
  24.  
  25. d[i][1] => Max(d[i-2][1], d[i-2][2]) + a[i]
  26. => d[i-1][] <== 아하.. 해보니깐 1번 연속, 2번 역속을 넣을 수가 없구나,,
  27.  
  28. d[i][2] =>= d[i-1][1] + a[i]
  29.  
  30.  
  31. d[1][1] = a[i];
  32. d[1][2] = 0;
  33.  
  34. */
  35.  
  36.  
  37. long d[301][3];
  38. int a[301];
  39.  
  40. long Max(long a, long b) {
  41. return a > b ? a : b;
  42. }
  43.  
  44. long go(int i, int j) {
  45. if (i == 0) return 0; //(wik) later I found
  46. if (i == 1) {
  47. if (j == 1) return a[i];
  48. if (j == 2) return 0;
  49. }
  50.  
  51. if (d[i][j] > 0) return d[i][j];
  52.  
  53. long max = 0;
  54. if (j == 1) {
  55. max = Max(go(i - 2, 1), go(i - 2, 2)) + a[i];
  56. }
  57. if (j == 2) {
  58. max = go(i - 1, 1) + a[i];
  59. }
  60.  
  61. d[i][j] = max;
  62. return d[i][j];
  63. }
  64.  
  65.  
  66. int main() {
  67. //freopen("input.txt", "r", stdin);
  68.  
  69. int n;
  70. cin >> n;
  71. for (int i = 1; i <= n; i++) {
  72. cin >> a[i];
  73. }
  74.  
  75. long max = 0;
  76. long temp = go(n, 1);
  77. if (temp > max) max = temp;
  78. temp = go(n, 2);
  79. if (temp > max) max = temp;
  80.  
  81. cout << max << endl;
  82.  
  83. return 0;
  84. }
Add Comment
Please, Sign In to add comment