Editorial for Atcoder Educational DP Contest C - Vacation

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: dquynh_2811

Độ phức tạp: ~O(N)~

Gọi dp[i][j] (~i: 1 \rightarrow n, j: 0 \rightarrow 2~ đại diện cho các hoạt động ~A~, ~B~, ~C~) là số điểm hạnh phúc tối đa mà Taro có thể nhận được khi tham gia các hoạt động trong ~i~ ngày đầu tiên mà hoạt động thực hiện vào ngày thứ ~i~ là hoạt động ~j~. Với điều kiện Taro không thể thực hiện các hoạt động giống nhau trong hai hoặc nhiều ngày liên tiếp, ví dụ như vào ngày thứ ~i~, Taro muốn tham gia hoạt động ~A~, thì ngày thứ ~i-1~, Taro chỉ có thể thực hiện các hoạt động ~B~ hoặc ~C~ nên ta có công thức QHĐ sau:

~dp[i][j] = max_{k≠j} (dp[i−1][k]+V[j])~

Với dp[i][j] khởi tạo nhận giá trị bằng ~0~. Kết quả cần tìm chính là ~max(dp[N][0],~ ~dp[N][1],~ ~dp[N][2]).~

#include <bits/stdc++.h>

using namespace std;

const int mx = 1e5 + 11;

int dp[mx][3];

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int N; cin >> N;

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

    cout << max({dp[N][0], dp[N][1], dp[N][2]}) << endl;
}

Comments

Please read the guidelines before commenting.


  • -38
    madinhdinh  commented on Oct. 30, 2022, 4:19 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 13
      darkkcyan  commented on Oct. 30, 2022, 4:25 a.m. ← edit 2

      Không phải ~50011~ là 5e4+11 à bạn?


  • 2
    thanh20092007  commented on Sept. 27, 2022, 1:47 a.m. ← edited

    V[j] là gì mn ơi


    • 5
      tachithanhdanh  commented on Sept. 27, 2022, 3:17 a.m.

      theo như code mẫu thì V[j] là số điểm hạnh phúc của hoạt động j vào thời điểm đang xét (vào ngày thứ i) á bạn


      • 2
        thanh20092007  commented on Sept. 27, 2022, 3:34 a.m.

        cảm ơn bạn nhiều nhá