P1668USACO04DECCleaningShiftsS-洛谷分析这道题最快的做法应该是贪心，但是线段树优化DP也可以做。首先看到此题，可以想到一个很暴力的区间DP：\(f[i][j]\)表示在\([i,j]\)时段内最少需要的奶牛数量。对于每头牛的空闲时段\([l,r]\)，其每个子区间答案均为\(1\)；对于

原题链接题解1.朴素想法，每头牛要么值班要么不值班，搜索遍历所有情况\(O(2^n)\)2.稍作修改，如果一头牛值班，那么在它值班结束时间之前值班的牛的数量一定是最优的，\(o(nT)\)3.换个思路，已知要覆盖\([1,T]\)这个时间段，所以左端点为\(1\)的牛必须选一个，且选右端点最大的那个，设这