POJ 1821 单调队列+dp

时间:2022-02-17 09:55:59

题目大意:有K个工人,有n个墙,现在要给墙涂色。然后每个工人坐在Si上,他能刷的最大范围是Li,且必须是一个连续子区间,而且必须过Si,他刷完后能获得Pi钱

思路:定义dp[i][j]表示前i个人,涂色到j的最大的val是多少。

转移就是dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) 和dp[i][j] = max(dp[i][j], dp[i - 1][z] + (j - z) * p[i]); 当然z是有条件范围的,这个请自己找。。。

然后这样子转移的话复杂度就是k*n*l,所以复杂度超了,因此我们要用单调队列维护这个l,让他变为o(1)。然后我们发现l的转移条件是可以通过deque来获得的,所以我们只要维护这个deque就行了