题解 P2938 【[USACO09FEB]股票市场Stock Market】

· · 题解

题意简述：

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

题目分析：

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

题解：

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

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

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

代码

PS:尽量最后再看