372c专题

codeforces 372C Watching Fireworks is Fun 单调队列优化dp

题意:一个城镇有n个区域,从左到右1-n,每个区域之间距离1个单位距离。节日中有m个烟火要放,给定放的地点a[ i ]、时间t[ i ] ,如 果你当时在区域x,那么你可以获得b[ i ] - | a[ i ] - x |的happiness 。你每个单位时间可以移动不超过d个单位距离,你的初始位置是任意 的,求你通过移动能获取到的最大的happiness值。 思路: 首先设dp[i]