令 \(f_i\) 表示前 \(i\) 头牛的总用时，很容易写出转移方程 \(f_i=\min\{f_j+sum(j,i)\}\)。其中 \(sum(j,i)\) 表示 \(j\sim i\) 中食品的种类。
直接暴力做是 \(O(N^2)\) 的，考虑优化。发现 \(f\) 数组单调不降，在 \(sum(j,i)\) 相同时，\(j\) 取最小最优。而答案最大是 \(N\)（每头牛都单独分一组），所以 \(sum(j,i)\) 最大取 \(\lfloor\sqrt N\rfloor\) 否则显然不优。
然后就很简单了，我们只需对 \(sum(j,i)\) 的每种取值都维护 \(j\) 的最小值即可。