【BZOJ1855】股票交易（动态规划，单调队列）

题面

BZOJ

题解

很显然，状态之和天数以及当天剩余的股票数有关

设\(f[i][j]\)表示第\(i\)天进行了交易，剩余股票数为\(j\)的最大获利

每次枚举可以转移过来的天数以及股票数

再枚举买入或者卖出的数量，

时间复杂度\(O(T^2Mp^2)\),30pts（但是有40pts。。。）

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 2222

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int T,Mp,W;

int f[MAX][MAX];

int vb[MAX],vs[MAX],lb[MAX],ls[MAX];

int main()

{

    T=read();Mp=read();W=read();

    for(int i=1;i<=T;++i)

    {

        vb[i]=read();vs[i]=read();

        lb[i]=read();ls[i]=read();

    }

    memset(f,-63,sizeof(f));

    f[0][0]=0;

    for(int i=1;i<=T;++i)

    {

        for(int j=0;j<=max(i-W-1,0);++j)

        {

            for(int k=0;k<=Mp;++k)

            {

                for(int l=1;k+l<=Mp&&l<=lb[i];++l)

                    f[i][k+l]=max(f[i][k+l],f[j][k]-l*vb[i]);

                for(int l=1;l<=k&&l<=ls[i];++l)

                    if(l<=k)f[i][k-l]=max(f[i][k-l],f[j][k]+l*vs[i]);

            }

        }

    }

    int ans=0;

    for(int i=1;i<=T;++i)ans=max(ans,f[i][0]);

    printf("%d\n",ans);

    return 0;

}

其实没有任何必要枚举可以转移过来的天数

把状态稍微改变一下

设\(f[i][j]\)表示第\(i\)天拥有的股票数为\(j\)的最大获利

每次可以从\(f[i-1]\)转移过来

这样只需要枚举交易的限制天数前就行了

复杂度\(O(TMp^2)\),50pts

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 2222

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int T,Mp,W;

int f[MAX][MAX];

int vb[MAX],vs[MAX],lb[MAX],ls[MAX];

int main()

{

	T=read();Mp=read();W=read();

	for(int i=1;i<=T;++i)

	{

		vb[i]=read();vs[i]=read();

		lb[i]=read();ls[i]=read();

	}

	memset(f,-63,sizeof(f));

	int ttt=f[0][0];

	f[0][0]=0;

	for(int i=1;i<=T;++i)

	{

		int j=max(0,i-W-1);

		for(int k=0;k<=Mp;++k)

		{

			f[i][k]=max(f[i][k],f[i-1][k]);

			for(int l=1;k+l<=Mp&&l<=lb[i];++l)

				f[i][k+l]=max(f[i][k+l],f[j][k]-l*vb[i]);

			for(int l=1;l<=k&&l<=ls[i];++l)

				if(l<=k)f[i][k-l]=max(f[i][k-l],f[j][k]+l*vs[i]);

		}

	}

	printf("%d\n",f[T][0]);

	return 0;

}

听说数据比较水，50pts稍微优化一下可以卡过70pts

70pts:

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 2222

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int T,Mp,W;

int f[MAX][MAX];

int vb[MAX],vs[MAX],lb[MAX],ls[MAX];

int main()

{

	T=read();Mp=read();W=read();

	for(int i=1;i<=T;++i)

	{

		vb[i]=read();vs[i]=read();

		lb[i]=read();ls[i]=read();

	}

	memset(f,-63,sizeof(f));

	f[0][0]=0;

	for(int i=1;i<=T;++i)

	{

		for(int j=0;j<=lb[i];++j)f[i][j]=-j*vb[i];

		for(int j=0;j<=Mp;++j)f[i][j]=max(f[i][j],f[i-1][j]);

		if(i<=W)continue;

		int j=i-W-1;

		for(int k=0;k<=Mp;++k)

		{

			for(int l=1;k+l<=Mp&&l<=lb[i];++l)

				f[i][k+l]=max(f[i][k+l],f[j][k]-l*vb[i]);

			for(int l=1;l<=k&&l<=ls[i];++l)

				if(l<=k)f[i][k-l]=max(f[i][k-l],f[j][k]+l*vs[i]);

		}

	}

	printf("%d\n",f[T][0]);

	return 0;

}

这个复杂度已经跑不了了

怎么解决转移的复杂度问题？

对于从\(W\)天(第\(x\)天)前购买/出售的转移

我们额外看看：

\(f[i][j]=max(f[x][k]+k*V-j*V)\)

貌似和\(j\)没什么关系诶

\(f[i][j]=max(f[x][k]+k*V)-j*V\)

这样就可以单调队列优化转移了

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 2222

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int T,Mp,W;

int f[MAX][MAX];

int vb[MAX],vs[MAX],lb[MAX],ls[MAX];

int l,r,Q[MAX];

int main()

{

	T=read();Mp=read();W=read();

	for(int i=1;i<=T;++i)

	{

		vb[i]=read();vs[i]=read();

		lb[i]=read();ls[i]=read();

	}

	memset(f,-63,sizeof(f));

	f[0][0]=0;

	for(int i=1;i<=T;++i)

	{

		for(int j=0;j<=lb[i];++j)f[i][j]=-j*vb[i];

		for(int j=0;j<=Mp;++j)f[i][j]=max(f[i][j],f[i-1][j]);

		if(i<=W)continue;

		int x=i-W-1,h,t;

		h=1,t=0;

		for(int j=0;j<=Mp;++j)

		{

			while(h<=t&&Q[h]<j-lb[i])++h;

			while(h<=t&&f[x][Q[t]]+Q[t]*vb[i]<=f[x][j]+j*vb[i])--t;

			Q[++t]=j;

			if(h<=t)f[i][j]=max(f[i][j],f[x][Q[h]]+Q[h]*vb[i]-j*vb[i]);

		}

		h=1,t=0;

		for(int j=Mp;j>=0;--j)

		{

			while(h<=t&&Q[h]>j+ls[i])++h;

			while(h<=t&&f[x][Q[t]]+Q[t]*vs[i]<=f[x][j]+j*vs[i])--t;

			Q[++t]=j;

			if(h<=t)f[i][j]=max(f[i][j],f[x][Q[h]]+Q[h]*vs[i]-j*vs[i]);

		}

	}

	printf("%d\n",f[T][0]);

	return 0;

}

最新文章

  1. BIAWGN信道
  2. django--app（六）
  3. 【HDOJ】3601 Coach Yehr’s punishment
  4. Python自动化运维之22、JavaScript
  5. 网站飘窗js代码
  6. swift 2 选择头像图片
  7. jquery.validate提示错误方法
  8. 剑指offer面试题3 二维数组中的查找 （java）
  9. 一键安装Cloud Torrent
  10. ES--07
  11. index-document-shard
  12. HTTP方法之GET与POST对比
  13. October 31st, 2017 Week 44th Tuesday
  14. JS基础（一）异常错误
  15. 更新image的方法
  16. Android下Notification,样式style,主题theme的功能实现
  17. sublime Text快捷键(超级全）
  18. [LeetCode] 30. Substring with Concatenation of All Words ☆☆☆
  19. setup factory 打包VB 工程
  20. Json映射为Map，避免定义过多pojo类

热门文章

  1. Material使用11 核心模块和共享模块、 如何使用@angular/material
  2. a:hover 等伪类选择器
  3. 阿里云 virtual memory exhausted: 无法分配内存
  4. 关于Apache配置虚拟主机后在局域网中让其他电脑访问
  5. 洛谷 P4016负载平衡问题【费用流】题解+AC代码
  6. php提供的sapi有哪些？CGI、FastCGI、php-fpm、php-cgi解释
  7. Windows Server 2016-图形化备份域控制器
  8. 17_8_9 Spring 注入
  9. 老男孩Python全栈开发（92天全）视频教程 自学笔记07
  10. Android开发之Android&#160;Context&#160;Menu