正解:dp+单调队列优化
解题报告:
先放个传送门鸭qwq
umm首先dp转移挺好想的?就买和不买 f[i][j]表示第i天手上有j的股份的最多钱,转移也很好想?就枚举第1天到第i-w-1天枚举买k股,然后n3转移嘛,挺无脑的?
然后重点在于怎么优化qwq
显然i和j是不可能再优化了的,所以只能考虑从k方面下手
然后考虑到其实买入和卖出直接其实是毫无关联的(我知道会影响操作时间,,,这个无伤大雅嘛我值得是他们的值不会互相有影响嘛QwQ)所以我们这里强行当做只讨论卖出
发现对于k有个限制条件:k<=bsi
看到这个就应该能想到辣?
于是就单调队列优化一波鸭,维护一个f递减j递增的单调队列就好
具体看代码,感jio还是讲的比较清楚辣!over!