UVA 10020

Đề bài: https://uva.onlinejudge.org/external/100/10020.pdf
Ý tưởng:
Sắp xếp lại các đoạn tăng dần theo tọa độ left và đi xét lần lượt các đoạn theo thứ tự này để chọn ra các đoạn phủ tối thiểu theo quy tắc:

• Đầu tiên, gán giá trị phải nhất hiện tại curr = 0.
• Ở mỗi lần chọn ta sẽ chọn 1 đoạn sao cho đoạn này có tọa độ left nhỏ hơn hoặc bằng giá trị phải nhất hiện tại và tọa độ right là lớn nhất có thể, sau khi chọn đoạn này ta cập nhật lại giá trị curr.

Đoạn con có tổng lớn nhất

BÀI TOÁN

Cho một dãy gồm n số nguyên a1, a2, …, an. Hãy tìm một đoạn con (dãy gồm các phần tử liên tiếp nhau) có tổng lớn nhất.

Dữ liệu vào:

• Dòng đầu ghi số n
• Dòng thứ hai ghi n số nguyên a1, a2, …, an, mỗi số có giá trị tuyệt đối không vượt quá 1000.

Kết quả:

Ghi ra 1 số là tổng lớn nhất tìm được.

Đề thi học sinh giỏi tin học TP. Cần Thơ 2014-2015

Bài	Tên bài	File chương trình	File dữ liệu vào	File kết quả
1	Tôi là đầu bếp	chief.*	chief.inp	chief.out
2	Thuật toán MDA	mda.*	mda.inp	mda.out
3	Biến đổi gen	dna.*	dna.inp	dna.out
4	Trò chơi lưới mê cung	maze.*	maze.inp	maze.out
5	Xếp hàng	queue.*	queue.inp	queue.out

UVA 10130 - SuperSale (Siêu khuyến mãi)

Link bài gốc
Link chấm bài

Có một chương trình bán hàng siêu khuyến mãi tại siêu thị SuperHyperMarket. Khi mua sắm ở đây, với mỗi mặt hàng, khách hàng có thể chọn mua cho mình với số lượng tối đa là 1 với giá cực kỳ rẻ. Ví dụ, một khách hàng có thể mua sắm: 1 tivi, 1 củ cà rốt. Chúng ta đi cùng một đại gia đình đến siêu thị này để mua sắm. Mỗi thành viên trong gia đình có thể mua sắm nhiều mặt hàng. Chúng ta được cho danh sách các mặt hàng với giá thực thế và khối lượng của nó. Và chúng ta cũng được biết, khối lượng tối đa mà mỗi thành viên trong gia đình có thể mang về. Vấn đề đặt ra là tính giá trị lớn nhất của các mặt hàng mà gia đình chúng ta có thể mua sắm.

Bài toán ba lô có số lượng đồ vật không hạn chế

BÀI TOÁN

Cho n vật có khối lượng lần lượt là a1, a2, …, an và giá trị lần lượt là v1, v2, …, vn, mỗi vật có số lượng không hạn chế.

Cho một ba lô có tải trọng là m

Yêu cầu chọn một số vật để vào ba lô sao cho tổng khối lượng của các vật không vượt quá m và tổng giá trị của các vật là lớn nhất có thể.

Một số bài tập sắp xếp và tìm kiếm

Codeforces 141A - Amusing Joke
Codeforces 160A - Twins
Codeforces 339A - Helpful Maths 
Codeforces 405A - Gravity Flip
Codeforces 490A - Team Olympiad
Codeforces 507A - Amr and Music
Codeforces 37A - Towers
Codeforces 479C - Exams
Codeforces 471B - MUH and Important Things
Codeforces 160B - Unlucky Ticket

Bài toán cái ba lô 0-1 (mỗi đồ vật có số lượng 1)

BÀI TOÁN

Cho n vật có khối lượng lần lượt là a1, a2, …, an và giá trị lần lượt là v1, v2, …, vn

Cho một ba lô có tải trọng là m

Yêu cầu chọn một số vật để vào ba lô sao cho tổng khối lượng của các vật không vượt quá m và tổng giá trị của các vật là lớn nhất có thể.

Bài toán dãy con tăng dài nhất

BÀI TOÁN

Cho một dãy gồm n số nguyên a1, a2, ..., an. Hãy tìm dãy con tăng dài nhất của dãy đã cho.

Dữ liệu:

- Dòng đầu tiên ghi số n

- Dòng thứ hai ghi n số nguyên.

Kết quả:

- Dòng đầu tiên ghi số k cho biết độ dài của dãy con tăng tìm được

- Dòng thứ hai ghi k số cho biết dãy con tăng tìm được