USACO 2022 US Open Contest, Platinum, 262144 Revisited
Xem PDFBessie rất thích tải game về để giải trí sau những giờ học căng thẳng trên chiếc điện thoại của cô nàng dù cho chiếc màn hình bé nhỏ của điện thoại gây ra nhiều khó khăn cho cô nàng khi sử dụng (móng của nàng bò này rất to!!!!).
Cô nàng thường xuyên bị cuốn hút bởi tựa game hiện tại mà cô ta chơi. Tựa game đó có thể mô tả như sau: ban đầu sẽ có dãy gồm \(N\) \((1 \le N \le 262144)\) số nguyên dương \(a_1, a_2, \dots, a_N\) \((\forall i \in [1 \dots N], 1 \le a[i] \le 10^6)\), ở mỗi lượt chơi Bessie chọn \(2\) số liên tiếp cạnh nhau và thay thế chúng bằng một số nguyên lớn hơn hai số này (VD: cô nàng có thể thay cặp số cạnh nhau \((5, 7)\) bằng một số nguyên mới là \(8\)). Tựa game sẽ kết thúc sau \(N - 1\) lượt chơi, lúc này chỉ còn lại một số duy nhất trong dãy, mục tiêu của trò chơi là phải cực tiểu hoá số cuối cùng này.
Bessie biết rằng trò cái game này quá đỗi dễ dàng cho bạn, cho nên Bessie muốn bạn không chỉ chơi game tối ưu trên riêng dãy \(a\) mà còn phải chơi trên tất cả dãy con liên tiếp của dãy \(a\) nữa.
Hãy cho biết tổng tất cả các số bé nhất bạn có thể đạt được cho từng dãy trong \(\frac{N(N + 1)}{2}\) dãy con liên tiếp của \(a\) nhé.
Input
- Dòng đầu tiên là số \(N\).
- Dòng thứ \(2\) là các số \(a_1, a_2, \dots, a_N\).
Output
- Một dòng duy nhất là kết quả của bài toán.
Scoring
- Subtask \(1\): \(N \le 300\).
- Subtask \(2\): \(N \le 3000\).
- Subtask \(3\): Tất cả các giá trị của dãy không vượt quá \(40\).
- Subtask \(4\): Dãy được cho là dãy không giảm.
- Subtask \(5\): Không có thêm ràng buộc.
Test 1
Input
6
1 3 1 2 1 10
Output
115
Note
Có tổng cộng \(\frac{6 \times 7}{2} = 21\) dãy con liên tiếp. Ví dụ một cách chơi tối ưu cho dãy con \([1, 3, 1, 2, 1]\) như sau:
- Ban đầu \(\rightarrow [1, 3, 1, 2, 1]\).
- Thay \((1, 3) \rightarrow 4\), dãy mới \(\rightarrow [4, 1, 2, 1]\).
- Thay \((2, 1) \rightarrow 3\), dãy mới \(\rightarrow [4, 1, 3]\).
- Thay \((1, 3) \rightarrow 4\), dãy mới \(\rightarrow [4, 4]\).
- Thay \((4, 4) \rightarrow 5\), kết quả cuối cùng là \(5\).
Dưới đây là kết quả cho các dãy con của ví dụ:
- Dãy \([1..1]\): \(1\).
- Dãy \([1..2]\): \(4\).
- Dãy \([1..3]\): \(5\).
- Dãy \([1..4]\): \(5\).
- Dãy \([1..5]\): \(5\).
- Dãy \([1..6]\): \(11\).
- Dãy \([2..2]\): \(3\).
- Dãy \([2..3]\): \(4\).
- Dãy \([2..4]\): \(4\).
- Dãy \([2..5]\): \(5\).
- Dãy \([2..6]\): \(11\).
- Dãy \([3..3]\): \(1\).
- Dãy \([3..4]\): \(3\).
- Dãy \([3..5]\): \(4\).
- Dãy \([3..6]\): \(11\).
- Dãy \([4..4]\): \(2\).
- Dãy \([4..5]\): \(3\).
- Dãy \([4..6]\): \(11\).
- Dãy \([5..5]\): \(1\).
- Dãy \([5..6]\): \(11\).
- Dãy \([6..6]\): \(10\).
Bình luận