banner

Bài tập: Cách chọn tối ưu

Đề bài
Mã bài: choose
Kiểu chấm: OI
Dữ liệu nhập: Nhập chuẩn
Kết quả xuất: Xuất chuẩn
Giới hạn thời gian: 1 giây
Được tạo bởi: Trợ giảng
Nội dung:

Cho mảng số nguyên dương a gồm n phần tử, khi chọn 1 phần tử vd: chọn a[i] thì kết quả sẽ cộng thêm a[i] điểm và xóa tất cả các phần tử có giá trị a[i]+1a[i]-1 khỏi mảng. tìm cách chọn sao cho được số điểm lớn nhất có thế.

Dữ liệu nhập:

- dòng đầu tiên chứa số n (1 ≤ n ≤ 105).
- dòng thứ hai chứa n số nguyên dương a1,a2,...an   (1a[i]≤105).

Dữ liệu xuất:

- số lớn nhất tìm được.

Ví dụ:

Nhập Xuất
3
1 2 3
4
9
1 2 1 3 2 2 2 2 3

10

 

 - Test 1: chọn a[1]=1 kết quả được 1 sau đó xóa phần tử có giá trị 0 & 2 => mảng còn: [3]. chọn 3 kết quả được 4.

- Test 2: chọn a[2]=2 kết quả được 2 sau đó xóa tất cả phần tử có giá trị 1 & 3 => mảng còn [2 2 2 2]. chọn lần lượt 4 số 2 nữa kết quả được 10.


Xem hướng dẫn cách làm bài
Để làm bài thì bạn cần phải đăng nhập