Phân Hoạch Đoạn Ổn Định
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề 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$
Community Discussion