Hi guys. Let's discuss this problem:
An array is good if the maximum element is no longer than the length.
The cost of the array is the length squared.
Divide the given array into several disjoint continuous parts so that each part is good and the total cost of all parts is the lowest possible.
Input In the first line, the positive integer n (1≤n≤100000) — the size of the array.
The next line contains n integers a1,a2,…,an(1≤ai≤n) Output Print the minimum possible total cost of all parts.
You can register on contest here: https://impact21.contest.codeforces.com/enter
Hi, I can't register on the content.
.
The problem was at the PreROI contest in Kazakhstan.
The main idea was D&C. Call recursion $$$calc(l, r)$$$ — that solves the problem for this range. Call recursion for the left side. For all elements on the right, let's find the optimal transition from the left side. Calculate prefix/suffix maximums for the right/left side respectively. Obvious that it will be monotonic. For each $$$r$$$ on the right, find all left borders — $$$l$$$, such that $$$[l; r]$$$ is good and make the transition from them. The possible values of $$$l$$$ will be an interval, so we can use some Convex Tree stuff + Segment Tree. Then call the recursion for the right side. There is actually a lot more to explain, but I think it's best to share the code. Because it's hard to explain in simple words :)
Code
Do you know this problem http://codeforces.net/blog/entry/87718 too?