Tìm tổng lớn nhất với phép toán xoá
Xem PDF
Điểm:
400
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
-Ta có một số \(T\) ban đầu có giá trị bằng \(0\)
-Cho một mảng \(a\) gồm \(n\) phần tử và một phép toán như sau:
- Chọn phần tử \(a_k(1\le k\le n)\) bất kỳ sau đó xoá đi tất cả các phần tử có giá trị \(a_k,a_k+1,a_k-1\) và cộng \(a_k\) vào \(T\)
Yêu cầu: Hãy thực hiện phép toán trên với một số lần tuỳ ý sao cho ta thu được giá trị \(T\) lớn nhất có thể. Giá trị \(T\) lớn nhất đó chính là kết quả cần tìm
Input
-
Dòng thứ nhất chứa số \(n(1\le n\le 10^5)\)
-
Dòng thứ hai chứa \(n\) số nguyên \(1\le a_i\le 10^5\) với \(1\le i\le n\)
Output
- In ra giá trị cần tìm
Example
Test 1
Input
3
3 2 1Output
4Note
- Đầu tiên: Ta chọn \(a[1]=3\) và sao đó xoá đi \(a[2]\) . Cộng \(a[1]\) vào \(T\) ta được \(T=3\). Lúc này mảng chỉ còn một phần tử có giá trị là \(1\). Và cộng nốt vào \(T\) ta được \(T=4\)
Bình luận
Viết đề không rõ yêu cầu ạ.
Đề ghi cộng ak vào T mà trên các test chấm thì phải cộng tất cả các giá trị ak vào T.
Bài này bị trùng ad ơi, cùng cách làm chỉ là thay problem statement
https://lqdoj.edu.vn/problem/reward
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.