💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
Dãy tăng có trọng số
wlis
Cho `n` phần tử. Phần tử thứ `i` có giá trị `v_i` và trọng số `w_i`. Bạn cần chọn một dãy con theo thứ tự chỉ số ban đầu: ```text i1 < i2 < ... < ik ``` sao cho: ```text v_i1 < v_i2 < ... < v_ik ``` Hãy tìm tổng trọng số lớn nhất có thể đạt được. ## Input ```text n v1 w1 v2 w2 ... vn wn ``` ## Output In ra tổng trọng số lớn nhất. ## Subtasks | Subtask | Ràng buộc gợi ý | Điểm | Hướng làm | |---|---:|---:|---| | 1 | `n ≤ 200` | 20 | DP `O(n^2)` | | 2 | Giá trị `v_i` nhỏ | 30 | Mảng max theo giá trị | | 3 | `n` lớn, `v_i` lớn | 50 | Nén tọa độ + Fenwick max | ## Ví dụ ### Input ```text 7 3 5 1 4 2 10 2 3 5 6 4 7 6 2 ``` ### Output ```text 23 ``` ### Giải thích ví dụ Một dãy con tối ưu là: ```text (1,4) -> (2,10) -> (4,7) -> (6,2) ``` Tổng trọng số: ```text 4 + 10 + 7 + 2 = 23 ``` Không thể chọn hai phần tử có cùng giá trị `2` liên tiếp vì điều kiện là tăng nghiêm ngặt.
✅ Đã AC: 0 / 0 submissions
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng