原题链接
首先有一个\(O(nk)\)的很显然的\(dp\),把荷斯坦牛看成\(1\),把更赛牛看成\(-1\),这样就可以很方便地通过前缀和来判断某一段中谁有优势了
考虑怎么优化,观察转移:
\[f[i]=min\{f[j]+[sum[i]-sum[j]\leqslant 0]\},1\leqslant i-j\leqslant k
\]
因为\([sum[i]-sum[j]\leqslant 0]\)只能为\(0\)或\(1\),那么我们开一个双关键字的单调队列维护一下就好了
代码在此:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include