Phân Hoạch Đoạn Ổn Định

Buổi 21 — DP 1D cổ điển Dynamic Programming dynamic-programming two-pointers
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho một dãy số nguyên $a_1, a_2, \dots, a_N$ và một số nguyên không âm $D$. Một đoạn con liên tiếp $a[l..r]$ được gọi là ổn định nếu hiệu giữa phần tử lớn nhất và phần tử nhỏ nhất trong đoạn đó không vượt quá $D$ (tức là $\max_{l \le k \le r} a_k - \min_{l \le k \le r} a_k \le D$).

Hãy đếm số cách chia toàn bộ dãy $a$ thành một hoặc nhiều đoạn con liên tiếp không giao nhau sao cho mỗi đoạn đều ổn định. Kết quả lấy phần dư khi chia cho $10^9 + 7$.

Cấu trúc con tối ưu: gọi $dp[i]$ là số cách chia $i$ phần tử đầu tiên. Với mỗi $i$, tồn tại chỉ số $L_i$ nhỏ nhất sao cho đoạn $[L_i + 1 .. i]$ ổn định; khi đó $dp[i] = \sum_{j = L_i}^{i-1} dp[j]$. Có thể tính trong $O(N)$ bằng hai con trỏ, hai hàng đợi đơn điệu và mảng cộng dồn.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N$ và $D$ ($1 \le N \le 10^5$, $0 \le D \le 10^9$).
  • Dòng thứ hai chứa $N$ số nguyên $a_1, \dots, a_N$ ($|a_i| \le 10^9$).
Dữ liệu ra
  • In ra số cách phân hoạch hợp lệ modulo $10^9 + 7$.
Ví dụ
Input Output
4 2\n1 3 2 4 7
3 0\n1 2 1 1
Giới hạn
  • $1 \le N \le 10^5$
  • $0 \le D \le 10^9$
  • $|a_i| \le 10^9$
Draft saved