Kì nghỉ của Kaninho

Xem PDF
Tác giả:
jumptozero
Dạng bài
Điểm: 350 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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 \(a_i,b_i,c_i(1\le a_i,b_i,c_i\le 10^4)\)

Output

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

Example

Test 1

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

Giải thích: \(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\)

Bình luận


  • 7
    VoBaThongL921    10:58 a.m. 20 Tháng 9, 2021 ← đã chỉnh sửa

    Trong độ hạnh phúc lớn nhất chắc chắn không có "làm bài tập về nhà"

    2 phản hồi

    • 6
      N7hoatt    10:38 a.m. 18 Tháng 8, 2020

      hóng bài mình vào editorial


      • 2
        quadangvaica    5:35 p.m. 14 Tháng 8, 2020

        hay quá :>


        • 67
          N7hoatt    4:27 p.m. 8 Tháng 8, 2020 ← chỉnh sửa 5

          HINT

          • Ta gọi \(L[i][1], L[i][2], L[i][3]\) là độ hạnh phúc lớn nhất có thể nhận khi chọn hành động \(a[i],b[i],c[i]\)

          • công thức quy hoạch động:

          \(L[i][1]=max(L[i][2], L[i][3])+a[i]\)

          \(L[i][2]=max(L[i][1], L[i][3])+b[i]\)

          \(L[i][3]=max(L[i][1], L[i][2])+c[i]\)

          kết quả cuối cùng là \(max(L[n][1], L[n][2], L[n][3])\)

          • để tiết kiệm bộ nhớ ta không cần lưu mảng \(a, b, c\) mà chỉ cần tái sử dụng biến \(a, b, c\)

          Renference AC Code | O(n)time | O(n*3)space | DP-general

              cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a>>b>>c;
        L[i][1]=max(L[i-1][2], L[i-1][3])+a;
        L[i][2]=max(L[i-1][1], L[i-1][3])+b;
        L[i][3]=max(L[i-1][1], L[i-1][2])+c;
    }
    cout<<max({L[n][1], L[n][2], L[n][3]});

          **p/s: thấy hay thì cho một upvote **

          2 phản hồi