VACATION - Kì nghỉ của Kaninho

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type
Allowed languages
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Kì nghỉ hè của (Kaninho) bắt đầu vào ngày mai, và anh ấy quyết định lên kế hoạch ngay từ bây giờ

Kì nghỉ gồm (N) ngày. Với mỗi (i(1\le i\le N)), (Kaninho) sẽ chọn (1) trong (3) hoạt động dưới đây và thực hiện nó vào ngày thứ (i) :

  • A: Đi bơi ở biển. Thu về (a_i) độ "hạnh phúc".
  • B: Đi bắt sâu bọ ở trên núi. Thu về (b_{i}) độ "hạnh phúc".
  • C: Làm bài tập về nhà. Thu về (c_i) độ "hạnh phúc".

Bởi vì (Kaninho) dễ dàng buồn chán, nên anh ấy không thể thực hiện hai hoạt động giống nhau trong (2) ngày (hoặc hơn) liên tiếp.

Tìm độ "hạnh phúc" lớn nhất mà (Kaninho) có thể đạt được.

Input

  • Dòng thứ nhất chứa số nguyên (N(1\le N\le 10^5))
  • (N) dòng tiếp theo, mỗi dòng chứa (3) số nguyên (ai,bi,ci(1\le ai,bi,ci\le 10^4))

Output

  • In ra độ "hạnh phúc" lớn nhất cần tìm

Sample

Input #1
3
10 40 70
20 50 80
30 60 90
Output #1
210

Hint

(Kaninho) sẽ thực hiện các hoạt động (C,B,C) theo thứ tự trong (3) ngày, và thu được độ hạnh phúc lớn nhất là (70+50+90=210)

Problem source: DP Contest Atcoder


Comments

Please read the guidelines before commenting.



  • 0
    hohoanghai5042011  commented on April 2, 2024, 8:23 a.m.

    include <iostream>

    include <vector>

    include <algorithm>

    using namespace std;

    int maxHappiness(int N, vector<int>& a, vector<int>& b, vector<int>& c) { vector dp(N + 1, vector<int>(3, 0));

    for (int i = 1; i <= N; ++i) {
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a[i - 1];
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + b[i - 1];
        dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + c[i - 1];
    }
    
    return max({dp[N][0], dp[N][1], dp[N][2]});
    

    }

    int main() { int N; cin >> N;

    vector<int> a(N), b(N), c(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i] >> b[i] >> c[i];
    }
    
    cout << maxHappiness(N, a, b, c) << endl;
    
    return 0;
    

    }