Tổng chênh lệch
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
cung cấp cho bạn dãy số nguyên gồm \(N\) phần tử.
Nhiệm vụ của bạn là thay đổi một vài giá trị trong dãy về bằng \(1\) (hoặc giữ nguyên) sao cho tổng các chênh lệch tuyệt đối giữa \(2\) phần tử liên tiếp là lớn nhất.
Input
- Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 5*10^5)\).
- Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_n ( 1 \le a_i \le 10^6)\)
Output
- Một số nguyên duy nhất là tổng trị tuyệt đối lớn nhất giữa \(2\) phần tử liên tiếp sau khi biến đổi.
Example
Test 1
Input
3
1 8 9
Output
14
Note
- Tổng ban đầu : \(|1 - 8| + |8 - 9| = 8\)
- Thay đổi : \([1, 8, 9] \rightarrow [1, 8, 1]\)
- Tổng lúc sau : \(|1 - 8| + |8 - 1| = 14\)
Scoring
- Subtask \(1\): (30 %) \(n \le 20\)
- Subtask \(2\): (30 %) \(n \le 10^3\)
- Subtask \(3\): (40 %) \(n \le 5 * 10^5\)
Bình luận
ai chỉ cho mình bài này được không?
-
7
NguyenPhuNhan
6:53 p.m. 16 Tháng 3, 2022
←
đã chỉnh sửa
→
-
1
huyhau6a2
7:08 p.m. 16 Tháng 3, 2022
-
1
PhanHuyKhang
7:37 p.m. 16 Tháng 3, 2022
-
2
huyhau6a2
8:21 p.m. 16 Tháng 3, 2022
←
đã chỉnh sửa
→
-
1
PhanHuyKhang
8:29 p.m. 16 Tháng 3, 2022
2 bình luận nữaĐặt dp[i][0] là cách chọn đạt được lớn nhất tính tới i với a[i] không giảm xuống 1.
dp[i][1] cx rứa mà a[i] giảm xuống còn 1
em ac rồi cảm ơn anh nha!
hihi ko khó lắm đâu
định đánh giá 400 đ ban đầu mà thôi, giờ giảm xuống 300!
=)) uk