自动搬运

查看原文

来自洛谷，原作者为

	ShineEternal **

搬运于2025-08-24 21:43:37，当前版本为作者最后更新于2018-10-10 17:32:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简述：

给定⼀个$D$天的$S$只股票价格矩阵，以及初始资⾦ $M$；每次买股票只能买某个股票价格的整数倍，可以不花钱，约定获利不超过$500000$。最⼤化你的 总获利。

题目分析：

首先我们要知道此题的详细意图：每天都可以用你手中有的钱买入股票，数量不限，也可以卖出你自己的股票，所得的收益或价值已经在$D*S$的矩阵中给出。要求在最后一天结束后得到的钱最多。

题解：

其实我们可以发现：对于每一天只要最大化你的收益就可以达成目的。然后问题就转换为求每一天的股票交易情况了。又知道每个股票可以无限量的购买（当然价值和不多于手中的钱），显然，就是一个完全背包。

其实题目中的获利不超过500000已经暗中提示了DP等算法的使用，因为给出一个不是由int到long long 的数据范围的改变一定是为数组内存准备的。

接下来就不再赘述了，其他部分会在代码中注明，看

代码

PS:尽量最后再看