背景：

代码贼短 . . . ... ...

题目传送门：

思路：

考虑 d p dp dp，设 f i , j f_{i,j} fi,j表示第 i i i天拥有 j j j股时的利润。 则： [ 1 ] [1] [1]考虑买入： f i , j = max ⁡ k = 1 j − 1 f k , j − 1 − a i f_{i,j}=max_{k=1}^{j-1}f_{k,j-1}-a_i fi,j=maxk=1j−1fk,j−1−ai； [ 2 ] [2] [2]考虑卖出： f i , j = max ⁡ k = 1 j − 1 f k , j − 1 + a i f_{i,j}=max_{k=1}^{j-1}f_{k,j-1}+a_i fi,j=maxk=1j−1fk,j−1+ai。 但这样会 T L E TLE TLE。

考虑一个小的差分，假设 a &lt; b &lt; c a&lt;b&lt;c a<b<c，显然让 c c c买 a a a更加优秀，那么可以表示为 ( c − b ) − ( b − a ) = c − a (c-b)-(b-a)=c-a (c−b)−(b−a)=c−a。 考虑每一次加入堆中两次。第一次维护当前已经买了前面的，但可能会被后面买，相当于当前不操作，直接让后面的买前面的；第二次维护当前被被后面买，但当前没有买前面的，相当于让后面的直接买当前的。

代码：

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
priority_queue<int,vector<int>,greater<int> > f;
	int n;
	LL ans=0;
int main()
{
          
   
	int x;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
          
   
		scanf("%d",&x);
		f.push(x),f.push(x);
		ans+=x-f.top();
		f.pop();
	}
	printf("%lld",ans);
}