Atcoder Educational DP Contest C - Vacation

Điểm: 0,25 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 1G

Input: stdin

Output: stdout

Người đăng:

dquynh_2811

Nguồn bài:

Atcoder Educational DP Contest

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Kỳ nghỉ hè của Taro bắt đầu vào ngày mai, nên anh ấy đã quyết định lên kế hoạch cho nó ngay bây giờ.

Kỳ nghỉ bao gồm N ngày. Vào ngày thứ ~i~ ~(1 \le i \le N)~, Taro sẽ chọn và tham gia một trong các hoạt động sau:

A: Bơi ở biển - nhận được ~a_i~ điểm hạnh phúc.
B: Bắt bọ trên núi - nhận được ~b_i~ điểm hạnh phúc.
C: Làm bài tập ở nhà - nhận được ~c_i~ điểm hạnh phúc.

Vì Taro dễ cảm thấy buồn chán nên anh không thể tham gia các hoạt động giống nhau trong hai ngày liên tiếp trở lên.

Tìm tổng số điểm hạnh phúc tối đa mà Taro có thể nhận được.

Input

Dòng đầu tiên là số nguyên ~N~ ~(1 \le N \le 10^5)~
Dòng thứ ~i~ trong số ~N~ dòng tiếp theo chứa ~3~ số nguyên ~a_i~, ~b_i~, ~c_i~ ~(1 \le a_i, b_i, c_i \le 10^4)~ lần lượt là điểm hạnh phúc có thể nhận được khi Taro tham gia hoạt động ~A, B, C~ của ngày thứ ~i~.

Output

In ra một số nguyên duy nhất là tổng điểm hạnh phúc tối đa mà Taro có thể nhận được.

Sample 1

Input

Output

Nếu Taro tham gia các hoạt động theo thứ tự ~C, B, C~, anh ấy sẽ có được ~70+50+90=210~ điểm hạnh phúc

Sample 2

Input

1
100 10 1

Output

Sample 3

Input

Output

Taro nên tham gia các hoạt động theo thứ tự : ~C, A, B, A, C, B, A~.

Bình luận

Hãy đọc nội quy trước khi bình luận.

-1

hoangquys đã bình luận lúc 16, Tháng 11, 2025, 10:48 ← chỉnh sửa →

include <bits/stdc++.h>

using namespace std;

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

vominhmanh10 đã bình luận lúc 31, Tháng 10, 2025, 10:31 ← chỉnh sửa →

quy hoạch động thôi, các trạng thái là tới ngày i, và ngày i đã chọn 1 trong 3 cái nào
vì không được 2 ngày liên tiếp trở lên nên chỉ xét dp[i - 1] với các lựa chọn khác lựa chọn đang dùng
dp[i][0] = a[i][0] + max(dp[i - 1][1] + dp[i - 1][2])...

n = int(input())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[0] * 3 for _ in range(n)]
dp[0][0] = a[0][0]
dp[0][1] = a[0][1]
dp[0][2] = a[0][2]
for i in range(1, n):
    dp[i][0] = a[i][0] + max(dp[i - 1][1], dp[i - 1][2])
    dp[i][1] = a[i][1] + max(dp[i - 1][0], dp[i - 1][2])
    dp[i][2] = a[i][2] + max(dp[i - 1][0], dp[i - 1][1])
print(max(dp[n - 1]))

-11

LVT_K66_TRANDUYBAO đã bình luận lúc 26, Tháng 7, 2025, 1:56

xin dowvote

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-14

vutuankiet đã bình luận lúc 19, Tháng 7, 2025, 15:40

xin downvote

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

1

HUNG2010 đã bình luận lúc 31, Tháng 5, 2025, 3:07

Code tham khảo: https://ide.usaco.guide/ORZ9PR885-KVvWChqfx

-14

NgocQuang đã bình luận lúc 20, Tháng 2, 2025, 0:29

ezzzzzzz

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-12

tanhphungvivo2009 đã bình luận lúc 13, Tháng 1, 2025, 11:53

ez no dif

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-26

khiemgia1105 đã bình luận lúc 4, Tháng 10, 2024, 7:48

Mn đăng kí khoắ học ở prf mình nhé, cam kết có giải

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-96

hanhsky đã bình luận lúc 29, Tháng 9, 2023, 10:13

include <bits/stdc++.h>

using namespace std;

define pb push_back

define fo(i, l, r , k) for(int i = l; i <= r; i += k)

define foi(i, l, r , k) for(int i = l; i >= r; i -= k)

define elif else if

define el cout << "\n";

define pii pair<int, int>

define fi first

define se second

define in(x) freopen(x, "r", stdin)

define out(x) freopen(x, "w", stdout)

define ll long long

define pob pop_back

define bs binary_search

define vii vector<int>

define low lower_bound

define up upper_bound

const int N = 1e5 + 11; const int inf = INT_MAX; const int mod = 1e9 + 7; int TC; int n ; int a[N][3]; ll f[N][3]; void inp() { cin >> n ; fo(i , 1 , n , 1) { fo(j , 1 , 3 , 1) { cin >> a[i][j]; } } } void sol() { fo(i , 1 , n , 1) { f[i][1] = max(f[i - 1][2] , f[i - 1][3]) + a[i][1]; f[i][2] = max(f[i - 1][1] , f[i - 1][3]) + a[i][2]; f[i][3] = max(f[i - 1][2] , f[i - 1][1]) + a[i][3]; } ll res = -inf; fo(j , 1 , 3 , 1) { res = max(res , f[n][j]); } cout << res << endl; } int main(){ TC = 1; while(TC--) { inp(); sol(); } return 0; } Xin downvote )):

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.