Quy hoạch động 2: Kỹ thuật cơ bản
40 bài về các kỹ thuật quy hoạch động cơ bản, độ khó tăng dần (rating 1500 đến 2000): QHĐ đoạn, cái túi biến thể, QHĐ bitmask, QHĐ chữ số, QHĐ trên cây và đổi gốc, QHĐ trên DAG, chuyển trạng thái bằng tổng tiền tố, dãy con tăng O(n log n), xác suất và kỳ vọng, QHĐ trên xâu.
Đề bài
40
Mã
Tên
Nhóm
Độ khó
Điểm
% AC
# AC
bubsortg
Điểm4,00
Đồ thị sắp xếp nổi bọt
LIS O(n log n): tập độc lập lớn nhất là dãy tăng
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
wordcombo
Điểm1,00
Tổ Hợp Từ
QHĐ xâu: đếm cách tách xâu thành từ (kết hợp trie)
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr09_paths
Điểm4,00
Đếm đường đi trên DAG
Đếm đường đi trên DAG theo thứ tự topo
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
dhbb26_dx11_11_a
Điểm4,00
Tổng các chữ số
QHĐ chữ số đếm tổng chữ số bằng S, tìm nhị phân
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
bbreedsi
Điểm1,00
Giống bò cân bằng (Dễ)
QHĐ xâu: chia dãy ngoặc thành hai dãy ngoặc đúng
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr13_indep
Điểm5,00
Tập độc lập trọng số lớn nhất trên cây
QHĐ cây cơ bản: tập độc lập trọng số lớn nhất
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
icpc24_mt_e
Điểm5,00
Thử thách trên đảo
BFS khoảng cách rồi QHĐ bitmask kiểu TSP
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
cntnums
Điểm1,00
Đếm Số
QHĐ chữ số: không có hai chữ số kề bằng nhau
Chưa phân loại
Tỷ lệ AC
100,0%
AC
2
cowrung
Điểm1,00
Chăn Bò Tối Ưu (Gold)
QHĐ đoạn trên trục số: khoảng đã thăm và đầu đứng
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
vertbook
Điểm5,00
Kệ sách của Shaass
Ba lô theo giá trị: chọn sách đứng tối ưu
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
elevride
Điểm1,00
Chuyến Thang Máy
QHĐ bitmask: số chuyến thang máy ít nhất
Chưa phân loại
Tỷ lệ AC
75,0%
AC
3
coincollect
Điểm1,00
Thu Thập Tiền Xu
Nén thành phần mạnh rồi QHĐ trên DAG
Chưa phân loại
Tỷ lệ AC
100,0%
AC
2
gr13_cover
Điểm5,00
Đặt bảo vệ trên cây
QHĐ cây 3 trạng thái: phủ đỉnh bằng bảo vệ
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
digitfree
Điểm5,00
Số sạch chữ số
QHĐ chữ số với bitmask các chữ số đã dùng
Chưa phân loại
Tỷ lệ AC
20,0%
AC
1
db_ts10_26_c
Điểm6,00
Dãy con tăng dài nhất
LIS O(n log n) tiền tố và hậu tố, ghép tại điểm cắt
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
writecode
Điểm6,00
Viết Code
Ba lô đếm hai chiều (số dòng, số lỗi)
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
cowdecathlon
Điểm1,00
Thi Đấu Mười Môn
QHĐ bitmask phân công kèm điểm thưởng theo tiền tố
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
chloeprz
Điểm6,00
Chloe và những phần quà
QHĐ cây: tổng cây con, hai cây con rời nhau lớn nhất
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
disttree
Điểm6,00
Khoảng cách trong cây
QHĐ cây đếm cặp đỉnh khoảng cách đúng k
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
cheaters
Điểm6,00
Bắt kẻ chép bài
Biến thể LCS: đoạn con có độ tương đồng lớn nhất
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
colorbrk
Điểm6,00
Tô màu dãy ngoặc
QHĐ đoạn trên dãy ngoặc với màu hai đầu
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
vtc05_fence
Điểm6,00
Sơn hàng rào
QHĐ đoạn: số lượt sơn ít nhất (strange printer)
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
nochange
Điểm1,00
Không Thối Tiền
QHĐ bitmask trên tập đồng xu kết hợp tìm nhị phân
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
treecost
Điểm6,00
Cây có chi phí lớn nhất
Đổi gốc (rerooting): chi phí lớn nhất trên cây
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gemjump
Điểm6,00
Thợ săn kho báu
QHĐ trên DAG trạng thái (vị trí, độ dài bước)
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
ridelift
Điểm6,00
Đi thang máy
QHĐ đếm với tổng tiền tố cho chuyển trạng thái đoạn
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
nolocmax
Điểm6,00
Dãy không có cực đại địa phương
QHĐ đếm khôi phục dãy, chuyển trạng thái bằng tổng tiền tố
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
badluck
Điểm6,00
Hòn đảo xui xẻo
QHĐ xác suất trên trạng thái ba loài
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
reqsubstr
Điểm1,00
Xâu Con Bắt Buộc
QHĐ trên automaton KMP: đếm xâu chứa mẫu
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
movrobots
Điểm1,00
Robot di chuyển
QHĐ xác suất trên lưới và kỳ vọng tuyến tính
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
distsubseq
Điểm1,00
Dãy Con Phân Biệt
QHĐ xâu đếm dãy con phân biệt
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
chocbar
Điểm7,00
Bẻ thanh sô cô la
QHĐ chia hình chữ nhật: bẻ sô cô la lấy k ô
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
rgtower
Điểm7,00
Tháp Đỏ-Xanh
Ba lô đếm: số cách xây tháp đỏ xanh cao nhất
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
fire
Điểm7,00
Hoả hoạn
Ba lô có hạn chót: sắp theo hạn rồi QHĐ thời gian
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
hamflights
Điểm1,00
Hành Trình Hamilton
QHĐ bitmask đếm đường đi Hamilton
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
applmtree
Điểm7,00
Cây của Appleman
QHĐ cây đếm cách cắt cạnh, mỗi phần một đỉnh đen
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0