网站首页
编程语言
数据库
系统相关
其他分享
编程问答
USACO04DEC
2024-10-24
P1668 USACO04DEC Cleaning Shifts S 题解
P1668USACO04DECCleaningShiftsS-洛谷分析这道题最快的做法应该是贪心,但是线段树优化DP也可以做。首先看到此题,可以想到一个很暴力的区间DP:\(f[i][j]\)表示在\([i,j]\)时段内最少需要的奶牛数量。对于每头牛的空闲时段\([l,r]\),其每个子区间答案均为\(1\);对于
2024-05-17
P1668 [USACO04DEC] Cleaning Shifts S
原题链接题解1.朴素想法,每头牛要么值班要么不值班,搜索遍历所有情况\(O(2^n)\)2.稍作修改,如果一头牛值班,那么在它值班结束时间之前值班的牛的数量一定是最优的,\(o(nT)\)3.换个思路,已知要覆盖\([1,T]\)这个时间段,所以左端点为\(1\)的牛必须选一个,且选右端点最大的那个,设这