Hoán Vị Cách Quãng
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một hoán vị $P$ của các số từ $1$ đến $N$ và dãy trọng số dương $W_1, W_2, \dots, W_N$.
Hãy chọn một dãy các chỉ số $1 \le i_1 < i_2 < \dots < i_k \le N$ sao cho:
- $P_{i_1} < P_{i_2} < \dots < P_{i_k}$
- Không có hai chỉ số liên tiếp nào được chọn đứng kề nhau trong mảng ban đầu (tức là $i_{t+1} - i_t \ge 2$ với mọi $1 \le t < k$).
Tìm tổng trọng số $\sum_{t=1}^k W_{i_t}$ lớn nhất có thể.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên dương $N$. Dòng thứ hai chứa $N$ số nguyên là hoán vị $P_1, P_2, \dots, P_N$. Dòng thứ ba chứa $N$ số nguyên dương $W_1, W_2, \dots, W_N$.
Dữ liệu ra
In ra một số nguyên duy nhất là tổng trọng số lớn nhất.
Ví dụ
| Input | Output |
|---|---|
| 5 1 2 3 4 5 10 20 30 40 50 |
90 |
| 4 1 3 2 4 100 1 1 100 |
200 |
Giới hạn
- $1 \le N \le 10^5$
- $1 \le W_i \le 10^9$
Community Discussion