LINK:股票交易

题目确实不算难 但是坑点挺多 关于初值的处理问题我就wa了两次。

所以来谢罪。

由于在手中的邮票的数量存在限制 且每次买入卖出也有限制。

必然要多开一维来存每天的邮票数量。

那么容易想到\(f_{i,j}\)表示到了第\(i\)天有\(j\)张邮票的最大赚钱值。

每次需要间隔W天进行操作 W变成W+1 那么在第i天能够转移的是 \(0~i-W\)这个区间了。

枚举前面哪一天 买入卖出k张邮票 就可以得到\(n^2m^2\)的做法.

容易想到我们只需要\(i-W\)这个地方的值即可 强制要求 \(i,j,k,i<j\) 有\(f_{i,k}\leq f_{j,k}\)显然这样做不会更差.

复杂度为\(nm^2\)枚举决策k的时候容易想到单调队列优化 那么复杂度为\(n\cdot m\)

关于初值的问题 每次对于\(0-L\)先进行强制赋值然后和前一天比max 这点容易想当然的写错...

05-04 00:21