正文

一本通1605股票交易(代码片段)

gaojunonly1  gaojunonly1  2023-03-09  580

关键词：

1605：股票交易

时间限制: 1000 ms 内存限制: 524288 KB

【题目描述】

原题来自：SCOI 2010

最近 lxhgww 又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。

通过一段时间的观察，lxhgww 预测到了未来 $T$

另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔 $W$

在第一天之前，lxhgww 手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然， $T$

【输入】

输入数据第一行包括三个整数，分别是 $T$

接下来 $T$

【输出】

输出数据为一行，包括一个数字，表示 lxhgww 能赚到的最多的钱数。

【输入样例】

【输出样例】

【提示】

数据范围与提示：

对于

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()

    ll s=0;
    bool f=0;
    char ch=‘ ‘;
    while(!isdigit(ch))
    
        f|=(ch==‘-‘);
        ch=getchar();
    
    while(isdigit(ch))
    
        s=(s<<3)+(s<<1)+(ch^48);
        ch=getchar();
    
    return (f)?(-s):(s);

#define R(x) x=read()
inline void write(ll x)

    if(x<0)
    
        putchar(‘-‘);
        x=-x;
    
    if(x<10)
    
        putchar(x+‘0‘);
        return;
    
    write(x/10);
    putchar((x%10)+‘0‘);
    return;

inline void writeln(ll x)

    write(x);
    putchar(‘
‘);
    return;

#define W(x) write(x),putchar(‘ ‘)
#define Wl(x) writeln(x)
const int N=2005;
int T,MaxP,W;
int dp[N][N];
int main()

//    freopen("trade1.in","r",stdin);
    int i,j,k;
    R(T); R(MaxP); R(W);
    memset(dp,-63,sizeof dp);
    for(i=1;i<=T;i++)
    
        int AP=read(),BP=read(),AS=read(),BS=read();
        for(j=1;j<=min(AS,MaxP);j++) dp[i][j]=-1*AP*j;
        for(j=0;j<=MaxP;j++) dp[i][j]=max(dp[i][j],dp[i-1][j]);
        if(i<=W+1) continue;
        for(j=1;j<=MaxP;j++)
        
            for(k=max(j-AS,0);k<j;k++)
            
                dp[i][j]=max(dp[i][j],dp[i-W-1][k]-AP*(j-k));
                /*
                    dp[i][j]=max(dp[i][j],dp[i-W-1][k]-AP*j+AP*k);
                    dp[i][j]=max(dp[i][j],(dp[i-W-1][k]+AP*k)-AP*j)
                    (dp[i-W-1][k]+AP*k)最大的单调队列队首
                */
            
        
        for(j=0;j<MaxP;j++)
        
            for(k=j+1;k<=min(MaxP,j+BS);k++)
            
                dp[i][j]=max(dp[i][j],dp[i-W-1][k]+(BP*(k-j)));
                /*
                    dp[i][j]=max(dp[i][j],dp[i-W-1][k]+BP*k-BP*j);
                    dp[i][j]=max(dp[i][j],(dp[i-W-1][k]+BP*k)-BP*j);
                    (dp[i-W-1][k]+BP*k)最大的单调队列队首
                */
            
        
    
    Wl(max(dp[T][0],0));
    return 0;

/*
input
5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1
output
3
*/

暴力代码

把式子拆开可得如下（暴力代码注释）

dp[i][j]=max(dp[i][j],dp[i-W-1][k]-AP*j+AP*k);
dp[i][j]=max(dp[i][j],(dp[i-W-1][k]+AP*k)-AP*j)
所以可以维护一个单调队列，(dp[i-W-1][k]+AP*k)最大的单调队列队首

另一个同理

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()

    ll s=0;
    bool f=0;
    char ch=‘ ‘;
    while(!isdigit(ch))
    
        f|=(ch==‘-‘);
        ch=getchar();
    
    while(isdigit(ch))
    
        s=(s<<3)+(s<<1)+(ch^48);
        ch=getchar();
    
    return (f)?(-s):(s);

#define R(x) x=read()
inline void write(ll x)

    if(x<0)
    
        putchar(‘-‘);
        x=-x;
    
    if(x<10)
    
        putchar(x+‘0‘);
        return;
    
    write(x/10);
    putchar((x%10)+‘0‘);
    return;

inline void writeln(ll x)

    write(x);
    putchar(‘
‘);
    return;

#define W(x) write(x),putchar(‘ ‘)
#define Wl(x) writeln(x)
const int N=2005,inf=0x3f3f3f3f;
int T,MaxP,W;
int dp[N][N];
struct Record

    int Shuz,Weiz;
Ddq[N];
int main()

//    freopen("trade1.in","r",stdin);
    int i,j,Head,Tail;
    R(T); R(MaxP); R(W);
    memset(dp,-63,sizeof dp);
    for(i=1;i<=T;i++)
    
        int AP=read(),BP=read(),AS=read(),BS=read();
        for(j=1;j<=min(AS,MaxP);j++) dp[i][j]=-1*AP*j;
        for(j=0;j<=MaxP;j++) dp[i][j]=max(dp[i][j],dp[i-1][j]);
        if(i<=W+1) continue;
        Head=1; Tail=0;
        for(j=0;j<=MaxP;j++)
        
            while(Head<Tail&&Ddq[Head].Weiz<j-AS) Head++;
            while(Head<=Tail&&dp[i-W-1][j]+AP*j>Ddq[Tail].Shuz) Tail--;
            Ddq[++Tail]=(Record)dp[i-W-1][j]+AP*j,j;
            dp[i][j]=max(dp[i][j],Ddq[Head].Shuz-j*AP);
        
        Head=1; Tail=0;
        for(j=MaxP;j>=0;j--)
        
            while(Head<Tail&&Ddq[Head].Weiz>j+BS) Head++;
            while(Head<=Tail&&dp[i-W-1][j]+BP*j>Ddq[Tail].Shuz) Tail--;
            Ddq[++Tail]=(Record)dp[i-W-1][j]+BP*j,j;
            dp[i][j]=max(dp[i][j],Ddq[Head].Shuz-j*BP);
        
    
    int ans=0;
    for(i=0;i<=MaxP;i++) ans=max(ans,dp[T][i]);
    Wl(ans);
    return 0;

/*
input
5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1
output
3
*/

单调队列优化

python取台湾场外交易股票价格。(代码片段)

查看详情

[scoi2010]股票交易(代码片段)

题目描述最近lxhgww又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。通过一段时间的观察，lxhgww预测到了未来T天内某只股票的走势，第i天的股票买入价为每股APi，第i天的股票卖出价为每股BPi（... 查看详情

动态规划股票交易(代码片段)

文章目录1.买卖股票的最佳时机1.1题目1.2分析1.3代码2.买卖股票的最佳时机II2.1题目2.2分析2.3代码3.最佳买卖股票时机含冷冻期3.1题目3.2分析3.3代码4.买卖股票的最佳时机含手续费4.1题目4.2分析4.3代码1.买卖股票的最佳时机1.1题目给... 查看详情

[scoi2010]股票交易(代码片段)

[SCOI2010]股票交易推荐的相关题目显示题目描述最近 lxhgww 又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。通过一段时间的观察，lxhgww 预测到了未来 T 天内某只股票的走... 查看详情

创业板股票提示没有交易权限，怎么开通创业板股票交易权限？(代码片段)

创业板股票提示没有交易权限，怎么开通创业板股票交易权限？创业板，又称二板市场（Second-boardMarket）即第二股票交易市场，是与主板市场（Main-BoardMarket）不同的一类证券市场，专为暂时无法在主板上市的创业型企业、中小... 查看详情

scoi2010股票交易(代码片段)

题目最近( extlxhgww)又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。通过一段时间的观察，( extlxhgww)预测到了未来(T)天内某只股票的走势，第(i)天的股票买入价为每股(ap_i)，第(i)天的股票卖出价... 查看详情

量化交易中，如何快速把股票代码转换成int整形？(代码片段)

...的大神沟通中，收到这样一个需求，需要快速把股票代码转换成整形变量，也就是需要把新收到的股票交易信息，迅速与历史的股票信息结合起来，从而通过交易策略快速决策。由于量化交易速度就是生命线... 查看详情

[bzoj1855][scoi2010]股票交易(代码片段)

Description最近lxhgww又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。通过一段时间的观察，lxhgww预测到了未来T天内某只股票的走势，第i天的股票买入价为每股APi，第i天的股票卖出价为每股BPi（... 查看详情

爬虫练习五：多进程爬取股市通股票数据

在上网查阅一些python爬虫文章时，看见有人分享了爬取股票的交易数据，不过实现得比较简单。这里就做个小练习，从百度股票批量爬取各股票的交易信息。文章出处为：Python爬虫实战(2)：股票数据定向爬虫。爬取数据：每... 查看详情

p2569股票交易(代码片段)

题目大意：你初始时有∞元钱，并且每天持有的股票不超过Maxp。有T天，你知道每一天的买入价格（AP[i]），卖出价格（Bp[i]），买入数量限制（AS[i]），卖出数量限制（BS[i]）。并且两次交易之间必须间隔W天。现在问你T天结束后... 查看详情

股票量化交易策略之选股模拟交易过程(代码片段)

...择，那么怎么结合筛选出来的多个因子来去选择某些股票2、回测选股方法多因子选股最常用的方法就是打分法和回归法，但是至于这两种哪个效果更好需要进行实际的模拟交易或者实盘交易之后才能确定。通常模拟交易... 查看详情

一本通提高数位动态规划windy数(代码片段)

传送门【一本通提高数位动态规划】windy数#include<bits/stdc++.h>usingnamespacestd;#definelllonglonglldp[15][15],ans;boolvis[15][15];lla[15];lll,r,len;lldfs(llpos,llpre,llzero,lllimit)if(pos>len)return1;if(!lim 查看详情

一本通1298：计算字符串距离(代码片段)

计算字符串距离同样也是字符串距离计算问题，参考一本通1276：【例9.20】编辑距离Code:#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;//Mystery_Sky//#defineINF0x3f3f3f3f#defineM3000intf[M][M];intlen_a 查看详情

一本通1295：装箱问题(代码片段)

装箱问题01背包的变式，费用=价值。#include<iostream>#include<cstdio>usingnamespacestd;//Mystery_Sky//#defineM100000intf[M],c[M];intv,m;intmain()scanf("%d%d",&v,&m);for(inti=1;i<=m;i+ 查看详情

一本通欧拉回路(代码片段)

欧拉回路1#include<bits/stdc++.h>2usingnamespacestd;3constintN=1e5+5,M=4e5+5;4intt,n,m,tot,in[N],ou[N],ans[M];5intcnt,fro[N],to[M],nxt[M];6boolvis[M];7voidadd(intx,inty)8to[++cnt]=y,nxt[cnt]=fro[x]; 查看详情

一本通确定进制(代码片段)

http://ybt.ssoier.cn:8088/problem_show.php?pid=1413注意一些细节问题就可以了。1、余数必定小于进制数2、注意判断数字范围1<=p,q,r<=1000000开始以为p*q会很大，但是实际p*q<=1000000;因为p*q=r<10000000;所以，本身没有必要使用高精度... 查看详情

一本通1297：公共子序列(代码片段)

公共子序列多组输入的最长公共子序列。#include<iostream>#include<cstdio>#include<cstring>#include<string>usingnamespacestd;//Mystery_Sky//#defineM1000strings1,s2;intf[M][M],len1,len2;intmain()whi 查看详情

scoi2010股票交易(代码片段)

题目链接：戳我看到这个题目，我们有一个朴素的DP想法（但是为什么我会先想到网络流啊喂，果然是菜鸡）设$dp[i][j][0/1/2]$表示第i天不进行交易/买入/卖出，现在手上有j张票，前i天能够获得的最大收益。转移什么的随便弄弄... 查看详情