【题解】血战二级市场
2023-03-15 19:01:58
发布于:浙江
98阅读
0回复
0点赞
血战二级市场
视频题解可点击此处查看
题目阅读
AC狗迷上了炒股,想要在二级市场赚钱。
市场中有一种概念叫做波幅,代表一段时间内股票的最高价和最低价的差额。
AC狗现在已经拿到了狗星农工科技公司连续N天的收盘价,他自己计算出了这N天的波幅,现在他想知道这N天出了空集之外所有连续子序列的波幅之和。
题意抽象
一个长度为n的序列Ai,求这个序列当中所有子序列(包括自身)当中,所有差值的和。
算法分析
面对求区间最大值问题,我们可以使用单调栈来解决这道题目。
在这道题目中,我们对于区间可以假设状态为f(i)或者f(i,j),进行转移。
设f(i)表示以i作为左端点的所有区间的最大值减最小值。
之后开始考虑状态转移:
假设f(i-1)进行转移,那么Ai便会更新一些区间的最大值或者最小值。
我们可以维护两个单调队列,一个上升,一个下降,符合Ai更新的特性。每次都算出更新的最大值和最小值的差进行累加即为答案。
代码讲解
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int N = 5e5+5;
const int INF = 1e9;
ll n,a[N],dp[N];
ll anser ;
ll s1[N],s2[N],w1[N],w2[N];
int t1,t2;
int main(){
cin >> n ;
for(int i = 1 ; i <= n ; i ++ ){
cin >> a[i];
dp[i] = dp[i-1];
ll sum = 0 ;
ll k = 0 ;
while(a[s1[t1]] < a[i] && t1){
k += w1[t1];
sum += (a[i] - a[s1[t1]]) * w1[t1] ;
t1 -- ;
}
s1[++t1] = i ;
w1[t1] = 1 + k ;
dp[i] += sum ;
sum = 0 ; k = 0 ;
while(a[s2[t2]] > a[i] && t2){
k += w2[t2];
sum += (a[s2[t2]]-a[i]) * w2[t2];
t2-- ;
}
s2[++ t2] = i;
w2[t2] = 1 + k;
dp[i] += sum;
anser += dp[i];
}
cout << anser << endl;
return 0;
}
全部评论 1
测试
2024-04-07 来自 浙江
1
有帮助,赞一个