P2943

令 $f_i$ 表示前 $i$ 头牛的总用时，很容易写出转移方程 $f_i=\min\{f_j+sum(j,i)\}$。其中 $sum(j,i)$ 表示 $j\sim i$ 中食品的种类。 直接暴力做是 $O(N^2)$ 的，考虑优化。发现 $f$ 数组单调不降，在 $sum(j,i)$ 相同时，$ ......