首页 > 代码库 > 股神小L 2016Vijos省选集训 day1
股神小L 2016Vijos省选集训 day1
股神小L (stock.c/pas/cpp)
============================
小L厌倦了算法竞赛，希望到股市里一展身手。他凭借自己还行的计算机功底和可以的智商，成功建立一个模型预测了一支股票接下来n天的价格。
我们把这支股票第i天的价格称为a_i。在接下来n天里，每一天小L可以选择花费a_i买入一股或者卖出一股从而获得a_i元收入。
当然小L卖出股票的时候，自己的账户上必须要有至少一股的剩余。现在小L希望知道，在n天过去之后，采取最优策略的情况下自己最多赚到多少钱。
注意小L家产万贯，可以视为初始本金为无穷，另外每一天小L能且只能进行一次买或卖的操作，不能什么都不做。
输入格式
一行一个数n，表示接下来n天
接下来了n行，每行一个正整数，表示股票在这一天的价格。
输出格式
一行一个整数，表示小L的最大获利，如果小L赔钱，则输出相应的负数
样例输入1
4
1 3 2 4
样例输出1
4
样例输入2
4
1 2 3 4
样例输出2
4
数据范围
对于10%的数据, 1 <= n <= 200
对于30%的数据, 1 <= n <= 3000
对于100%的数据, 1 <= n, a_i <= 200000
评测环境：Win7+Lemon
//100分贪心 #include<cstdio>#include<iostream>#include<ext/pb_ds/priority_queue.hpp>#define FRE(name) freopen(#name".in","r",stdin);freopen(#name".out","w",stdout);using namespace std;__gnu_pbds::priority_queue<int,greater<int> >q;inline int read(){ int x=0;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x;}const int N=2e5+5;int n,a[N];long long sum,ans;int main(){ FRE(stock) n=read(); for(int i=1;i<=n;i++) sum+=(a[i]=read()); for(int i=2,t;i<=n;i++){ if(i&1){ t=q.top(); if(a[i]>t){ ans+=a[i]-t;q.pop(); q.push(a[i]); } } else ans+=a[i],q.push(a[i]); } cout<<ans*2-sum; return 0;}/*30分 #include<cstdio>#include<cstring>#include<iostream>using namespace std;const int N=3005;const int inf=0x3f3f3f3f;int n,ans,a[N],f[N][N];int main(){ freopen("stock.in","r",stdin); freopen("stock.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++){ for(int j=0;j<=n;j++){ f[i][j]=-inf; } } //f[1][0]=0;WA*1 f[1][1]=-a[1]; for(int i=2;i<=n;i++){ for(int j=0;j<=n;j++){ if(f[i-1][j]!=-inf){ if(j<n) f[i][j+1]=max(f[i][j+1],f[i-1][j]-a[i]); if(j>0) f[i][j-1]=max(f[i][j-1],f[i-1][j]+a[i]); } } } for(int i=0;i<=n;i++) ans=max(ans,f[n][i]); printf("%d",ans); return 0;}*/
股神小L 2016Vijos省选集训 day1
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。