Advertisement
Josif_tepe

Untitled

Oct 18th, 2021
142
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.78 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. int n;
  5. int mat[100005][3];
  6. int memo[100005][3];
  7. int vacation(int i, int activity) {
  8.     if(i == n) {
  9.         return 0;
  10.     }
  11.     if(memo[i][activity] != -1) {
  12.         return memo[i][activity];
  13.     }
  14.     int result = 0;
  15.     for(int j = 0; j < 3; j++) {
  16.         if(activity != j) {
  17.             result = max(result, vacation(i + 1, j) + mat[i][activity]);
  18.         }
  19.     }
  20.     return memo[i][activity] = result;
  21. }
  22. int main() {
  23.     cin >> n;
  24.     for(int i = 0; i < n; i++) {
  25.         cin >> mat[i][0] >> mat[i][1] >> mat[i][2];
  26.         memo[i][0] = memo[i][1] = memo[i][2] = -1;
  27.     }
  28.     cout << max(vacation(0, 0) , max(vacation(0, 1) , vacation(0, 2)) ) << endl;
  29.     return 0;
  30. }
  31. // fib(7) = fib(6) + fib(5)
  32. //
  33.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement