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 这点容易想当然的写错...