视频剪辑软件 Hibernate unity 计算机网络 datetime Echojs angularjs版本 vue案例 mysql小数用什么类型 鼠标失去焦点事件 linux自动获取ip js字符串排序 kubernetes集群 java操作mysql java方法 java原始数据类型 java接口的修饰符 java数组排序 java常用数据结构 linux安装 黑帮之地修改器 微信助力软件 微信超级好友 音乐剪辑器下载 cf透视辅助 系统维护工具 魔兽改图工具 js小数点保留2位 小程序开发工具下载 js文件上传 jarsigner xmind画流程图 相册制作软件 软碟通u盘装系统教程 卧龙推广 汉仪旗黑字体下载 汪文君 jdk8安装教程 仁王木灵全收集 ps减去顶层
当前位置: 首页 > 学习教程  > 编程语言

【HDU3401】Trade——【Luogu_P2569】股票交易(有改动)

2020/8/11 18:49:53 文章标签:

题目描述

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

通过一段时间的观察,\text{lxhgww}lxhgww 预测到了未来 TT 天内某只股票的走势,第 ii 天的股票买入价为每股 AP_i,第 ii 天的股票卖出价为每股 BP_i ,但是每天不能无限制地交易,于是股票交易所规定第 i 天的一次买入至多只能购买 AS_i 股,一次卖出至多只能卖出 BS i股。

另外,股票交易所还制定了两个规定。为了避免大家疯狂交易,股票交易所规定在两次交易(某一天的买入或者卖出均算是一次交易)之间,至少要间隔 W 天,也就是说如果在第 i 天发生了交易,那么从第 i+1 天到第 i+W 天,均不能发生交易。同时,为了避免垄断,股票交易所还规定在任何时间,一个人的手里的股票数不能超过 MaxP。

在第 11 天之前,WW 手里有一大笔钱(可以认为钱的数目无限),但是没有任何股票,当然,T 天以后,WW 想要赚到最多的钱,聪明的程序员们,你们能帮助他吗?

输入格式
输入数据第一行包括 3 个整数,分别是 T,MaxP,W。

接下来 T 行,第 i 行代表第 i−1 天的股票走势,每行 4 个整数,分别表示 AP_i,\ BP_i,\ AS_i,\ BS_iAP i


输出格式
输出数据为一行,包括 1 个数字,表示WW能赚到的最多的钱数。

输入输出样例

输入 #1 复制
5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1
输出 #1 复制
3

思路:
设置两次单调队列,一次求卖出的,一次求买入的,这样就能避免卖出买入纵横交错,杂乱无章,毫无头绪
因为W+1W+1天才能进行一次交易,所以我们只能用iw1i-w-1作为前驱
那动态转移方程为:买入:f[i][j]=max(q[k][1]-jxa[i])
卖出:f[i][j]=max(q[k][1]-jxb[i])
再用单调队列维护就行

代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
int t, f[2001][2001], q[100010][2], a[2001], b[2001], as[2001], bs[2001];
int main()
{
	scanf("%d", &t);
	while(t--)
	{
		int w, t, maxp;
		scanf("%d%d%d", &t, &maxp, &w);
		for(int i=0; i<=2000; i++)
			for(int j=0; j<=2000; j++)
				f[i][j]=-2147483647;//初始化
		for(int i=1; i<=t; i++)
			scanf("%d%d%d%d", &a[i], &b[i], &as[i], &bs[i]);
		for(int i=1; i<=w+1; i++)
			for(int j=0; j<=as[i]&&j<=maxp; j++)
				f[i][j]=-j*a[i];//因为1-w+1这几天没有可用的前驱,所以直接让他们成为w+1-t的前驱
		for(int i=1; i<=t; i++)
		{
			for(int j=0; j<=maxp; j++)
				f[i][j]=max(f[i][j], f[i-1][j]);//假设这一天什么都不做
			int head=1, tail=0;
			if(i<=w+1)continue;
			int s=i-w-1;
			for(int j=0; j<=maxp; j++)
			{
				int sum=f[s][j]+j*a[i];
				while(head<=tail&&sum>q[tail][1])tail--;
				q[++tail][0]=j;
				q[tail][1]=sum;
				while(head<=tail&&j-q[head][0]>as[i])head++;
				f[i][j]=max(f[i][j], q[head][1]-j*a[i]);//买入
			}
			head=1, tail=0;
			for(int j=maxp; j>=0; j--)
			{
				int sum=f[s][j]+j*b[i];
				while(head<=tail&&sum>q[tail][1])tail--;
				q[++tail][0]=j;
				q[tail][1]=sum;
				while(head<=tail&&q[head][0]-j>bs[i])head++;
				f[i][j]=max(f[i][j], q[head][1]-j*b[i]);//卖出
			}
		}
		int ans=0;
		for(int j=0; j<=maxp; j++)
			ans=max(ans, f[t][j]);
		printf("%d\n", ans); 
	}
	return 0;
}

本文链接: http://www.dtmao.cc/news_show_100033.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?