Solution - P4597 序列 sequence

P4597 序列 sequence

idea：

贪心？大根堆， $DP$ 分析（不会）

解决方案：

首先，有一个显然的 $dp$ 方法：

令 $f_{i,j}$ 表示前 $i$ 个固定，第 $i$ 个放了第 $j$ 大的数的最小花费。 $B_j$ 表示第 $j$ 大的数的值。有 $dp$ 方程：

$$f_{i,j} = \min_{k\leq j} \{ f_{i-1,k}\} + \mid B_j - A_i\mid$$

这玩意求个前缀最小值就可以 $O(n^2)$ 了，但是通不过这道题。

然后去看题解，发现大佬都在分析凸包什么的，看不懂，只能看一个稍微平易近人的分析方法（类似于反悔贪心）。

假设现在加入一个数 $x$ ，已经搞好的数列的最大值为 $y$ 。那么如果 $x\geq y$ ，我们是不需要操作的。如果 $x < y$ ，那么我们可以在 $[x,y]$ 中找到一个值 $z$ ，让 $x$ 和 $y$ 都等于 $z$ 。显然最优是让 $x,y$ 都降到 $x$ 。

但这样是有问题的，因为 $y$ 降到 $x$ 后，前面的数列就不再单调不降了。那为何这样做是对的呢？我们来看看：

现在数列长这样：

5      .
4
3    .
2
1  .

现在飞进来一个 $2$ ，那么我们会想把数列变成这样：

5
4
3    . . .
2
1  .

花费了 $3$ 。但要是再飞进来一个 $2$ ，我们就想：要是当年把第三个和第四个数都降到 $2$ 就好了，这样可以在花费相同的情况下使最大值小一点。

目标是这样的：

5
4
3
2    . . . .
1  .

实际上只需要花费 $4$ 。如果我们不管数列是否合法的话，我们会这样：

5      .
4
3    .
2
1  .

变成：

5
4
3    . 
2      . .
1  .

变成：

5
4
3
2    . . . .
1  .

也就是说，这么做不仅可以使当前贡献计算正确，还可以为未来谋取最优解。

十行 $Code$ ：

#include<bits/stdc++.h>
using namespace std;typedef long long LL;
priority_queue<LL> q;LL ans;
signed main(){
	int n;cin>>n;while (n--){
		int x;cin>>x;q.push(x);
		if (q.top()>x) ans+=q.top()-x,q.pop(),q.push(x);
	}
	return cout<<ans,0;
}