【题解】 Stock Market 股票市场

题目描述

尽管奶牛们天生谨慎，她们仍然在住房抵押信贷市场中受到打击，现在她们开始着手于股市。 Bessie很有先见之明，她不仅知道今天 $S(2<=S<=50)$ 只股票的价格，还知道接下来一共 $D(2\le D\le 10)$ 天的（包括今天）。 给定一个 $D$ 天的股票价格矩阵$（1\le 价格\le 1000)$ 以及初始资金 $M(1\le M\le 200000)$，求一个最优买卖策略使得最大化总获利。每次必须购买股票价格的整数倍，同时你不需要花光所有的钱（甚至可以不花）。这里约定你的获利不可能超过 $500000$ 。 考虑这个牛市的例子（这是Bessie最喜欢的）。在这个例子中，有 $S=2$ 只股票和 $D=3$ 天。奶牛有 $10$ 的钱来投资。

以如下策略可以获得最大利润，第一天买入第一只股票。第二天把它卖掉并且迅速买入第二只，此时还剩下 $4$ 的钱。最后一天卖掉第二只股票，此时一共有 $4+20=24$ 的钱。

题解

在某一天，对于每一支股票，我们只有$3$种操作

1. 不买
2. 买了后在明天卖
3. 买了后在后面的某一天卖

这里的前两种操作都很简单，很好转移
但是第三种操作除非再加一层循环才能解决

于是我们把第$3$种方法转化为第$2$种

即在中间的那几天通过不断抵消（买入又卖出）最后达到效果

比如：我们要在第一天买，第三天卖

那么我们在第一天买，第二天卖后重新买入，第三天再卖也能达到效果

于是我们只需枚举天数，对于每一天，进行一次完全背包（因为可以购买多只股票），把每天赚的钱相加，便可求到最后赚的钱

CODE:

#include
#include
#include
using namespace std;
int p[55][15];
int dp[2000005];
int main(){
//	freopen("trade.in","r",stdin);
//	freopen("trade.out","w",stdout);int s,d;long long m;scanf("%d %d %lld",&s,&d,&m);for(int i=1;i<=s;i++){for(int j=1;j<=d;j++){scanf("%d",&p[i][j]);}}int maxn;for(int j=1;j<d;j++){maxn=-1;for(int i=1;i<=s;i++){for(int k=p[i][j];k<=m;k++){dp[k]=max(dp[k-p[i][j]]+(p[i][j+1]-p[i][j]),dp[k]);maxn=max(maxn,dp[k]);  }}m+=maxn;memset(dp,0,sizeof(dp));}printf("%lld",m);
return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！