Hoán Vị Cách Quãng

Buổi 39 — DP + Data Structures Dynamic Programming
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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:

  1. $P_{i_1} < P_{i_2} < \dots < P_{i_k}$
  2. 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$
Draft saved