Quy hoạch động 3: Nâng cao và tối ưu
40 bài quy hoạch động nâng cao, độ khó tăng dần (rating 2000 đến 2700): hàng đợi đơn điệu, bao lồi (CHT) và cây Li Chao, tối ưu chia để trị, tối ưu Knuth, Aliens trick, QHĐ kết hợp cây phân đoạn hoặc Fenwick, SOS DP, QHĐ trên cây nâng cao, QHĐ profile, lũy thừa ma trận, đếm nâng cao và kỳ vọng.
Đề bài
40
Mã
Tên
Nhóm
Độ khó
Điểm
% AC
# AC
segpart
Điểm7,00
Chia dãy thành đoạn
Tối ưu chia để trị: chia k đoạn, chi phí bình phương
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
strip
Điểm7,00
Cắt dải giấy
Deque + hai con trỏ cho chia đoạn tối thiểu
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
fireworks
Điểm7,00
Xem Pháo Hoa
DP theo vị trí, cửa sổ trượt bằng deque
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
chainsaw
Điểm7,00
Chi phí đốn cây
Bao lồi (CHT) với hệ số đơn điệu, deque O(n)
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
monsgame2
Điểm1,00
Trò Chơi Quái Vật II
Cây Li Chao cho hệ số không đơn điệu
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
sersub
Điểm7,00
Sereja và các dãy con
Fenwick đếm dãy con phân biệt có trọng số
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
okabewalk
Điểm7,00
Okabe đi dạo
Lũy thừa ma trận theo từng đoạn trần
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
icpc21_nat_h
Điểm7,00
Lát gạch hành lang
Lát domino: profile bitmask + lũy thừa ma trận
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
bakery
Điểm8,00
Tiệm bánh ngọt
Chia k đoạn, cây phân đoạn cộng đoạn lazy
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
compatnum
Điểm8,00
Số tương thích
SOS DP: tìm phần tử là tập con của phần bù
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
berfed
Điểm8,00
Liên bang hóa Berland
Cái túi trên cây, gộp cây con O(n^2)
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
phoenixpc
Điểm8,00
Bật dãy máy tính
DP đếm theo khối, chèn dần vào thứ tự
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
icpc22_mn_c
Điểm8,00
Di dời
Tối ưu Knuth cho chia K đoạn (K-median trên đường)
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
vadertree
Điểm8,00
Cây của Darth Vader
Truy hồi tuyến tính bậc 100 bằng ma trận
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
giantchess
Điểm8,00
Cờ vua khổng lồ
Bao hàm loại trừ trên các ô cấm
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
csp_tst_26_b
Điểm8,00
Mái che
Aliens trick (tham số lambda) + hai con trỏ
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
ck01part
Điểm8,00
Chia đoạn tối ưu
Chia đoạn max-min+C: ngăn xếp đơn điệu + segtree
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
redistrict
Điểm1,00
Phân Chia Khu Vực
Chia nhóm độ dài tối đa K, deque theo cặp khóa
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
levregion
Điểm8,00
Màn chơi và các vùng
Kỳ vọng hình học + chia để trị hoặc CHT
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
jzzhunum
Điểm8,00
Jzzhu và những con số
SOS DP kết hợp bao hàm loại trừ
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
lovehate
Điểm8,00
Yêu và Ghét
Ngẫu nhiên hóa + SOS trên tập con nhỏ
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
famroads
Điểm8,00
Famil Door và những con đường
Đổi gốc tính kỳ vọng độ dài chu trình
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
diamcut
Điểm8,00
Cắt cây theo đường kính
DP cây giới hạn đường kính, gộp theo độ sâu
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
catways
Điểm8,00
Đường đi và những chú mèo
Lũy thừa ma trận xen kẽ các sự kiện
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
abnperm
Điểm8,00
Cặp hoán vị bất thường (dễ)
DP số hoán vị theo nghịch thế, tổng tiền tố
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
neqneigh
Điểm8,00
Hàng xóm khác nhau
Bao hàm loại trừ trong DP + ngăn xếp đơn điệu
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
nametune
Điểm8,00
Đoán tên bài hát
DP xác suất theo thời gian, cập nhật trượt
Chưa phân loại
Tỷ lệ AC
100,0%
AC
1
lru
Điểm8,00
Bộ nhớ đệm LRU
DP xác suất trên bitmask trạng thái cache
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
dhbb26_dx24_11_c
Điểm8,00
Phân lô tài nguyên
Chia để trị, chi phí đoạn tính bằng con trỏ kiểu Mo
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
knuthdiv
Điểm9,00
Chia Mảng Knuth
Tối ưu Knuth cho DP khoảng O(n^2)
Chưa phân loại
Tỷ lệ AC
10,0%
AC
1
voi19_robot
Điểm9,00
Thử nghiệm robot
DP phích cắm (plug DP) trên lưới 3 hàng
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
split
Điểm9,00
Chia dãy
QHĐ động: segtree ma trận max-plus có cập nhật
Chưa phân loại
Tỷ lệ AC
100,0%
AC
1
tst22_field
Điểm9,00
Chia ruộng
Aliens trick kết hợp hàng đợi đơn điệu
Chưa phân loại
Tỷ lệ AC
100,0%
AC
1
nocross2
Điểm1,00
Không Được Cắt Nhau II
DP kiểu LCS thưa với cây phân đoạn
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
teambuild
Điểm1,00
Xây Dựng Đội
DP đếm cặp đội sau khi sắp xếp trộn
Chưa phân loại
Tỷ lệ AC
100,0%
AC
1