POJ3666 O(nlogn)根据数学特征使用单调队列完全代替dp o(n^2)解法

求一个距离a最小的单增序列b，a[i]严格单调增等价于a[i]-i的不减(不严格单调增)

以下是在大佬的博客里看到的(大佬从cf评论区搬运加注释的)

There is a very short (10 lines!) and fast O(nlgn) solution for Div1C, proposed by woqja125 :

Start by subtracting i from all A[i]. We’ll define fi(X) = Minimum operation to make A[1 … i] monotonically increasing, while keeping A[i] <= X. it’s easy to see that the recurrence is —

Min{|Ai — Y| } (Y <= X) if i == 1
Min{fi-1(Y) + |Ai — Y|} (Y<=X) otherwise.
Observation : fi is an unimodal function, which have a nonpositive integer slopes. Denote Opt(i) as a point X which makes fi(X) minimum.

We will maintain those functions and calculate the minimum. we examine two cases :

(Fi(X)的图像可以看成是Fi-1(X)和 |Ai — Y|这两个图像的叠加。 Fi(X)的图像总是斜率小于0且斜率绝对值递减的曲线,并且从Opt(i)开始变成水平)

Case 1 : Opt(i-1) <= A[i]. In this case, Opt(i) = A[i], and every point under A[i] have +1 slope.

Case 2 : Opt(i-1) > A[i]. This case is tricky. every point over A[i] have +1 slope, and every point under A[i] have -1 slope. Opt(i) is the point where slope of fi is changed into -1 -> 0. When observing the function, Fi(Opt(i)) = F(i-1)(Opt(i-1)) + Opt(i-1) — A[i].

为了求答案,只要维护好这个Fi(X)曲线就好。具体实现的时候,由于从Fi-1到Fi只和Opt(i-1)有关，我们用个大根堆保存好每一个斜率开始改变的点,然后每次取出最大的点就是

Opt(i-1). 具体实现看代码：

///By woqja125, contest: Codeforces Round #371 (Div. 1), problem: (C) Sonya and Problem Wihtout a Legend, Accepted, #

#include<stdio.h>
#include<queue>

int main()
{
    int n, t;
    long long ans = 0;
    std::priority_queue<int> Q;
    scanf("%d%d", &n, &t);
    Q.push(t);
    for(int i=1; i<n; i++)
    {
        scanf("%d", &t); t-=i;
        Q.push(t);   //Ai>=Opt(i-1)的时候仅仅增加了Ai这个转折点 
        if(Q.top() > t) //Ai<Opt(i-1)的时候 
        {
            ans += Q.top() - t;
            Q.pop();
            Q.push(t);  //t push了2次,为的是使得任意相邻的两点之间斜率相差1,即使两点可能重合 
        }
    }
    printf("%lld", ans);
    return 0;
}

加一点字极丑的说明(怕以后忘记是怎么思考的了)：