首页
Python
Java
前端
数据库
Linux
Chatgpt专题
开发者工具箱
poj2373专题
poj2373 Dividing the Path 单调队列dp
题意:在长为L的草地上装喷水头,喷射是以这个喷水头为中心,喷水头的喷洒半径是可调节的,调节范围为[a,b]。要求草地的每个 点被且只被一个喷水头覆盖,并且有些连续区间必须被某一个喷水头覆盖,而不能由多个喷头分段完全覆盖,求喷水头的最小数目。 思路:设dp[i]表示正好喷到i这个位置缩安放的最少喷泉数,那么dp[i]=min(dp[k])+1 (i - 2 * B <= k <= i -
阅读更多...