[POJ 1821] Fence【DP+单调队列优化】

  • 2018-01-24
  • 0
  • 0

Problem:

Time Limit: 1000MS Memory Limit: 30000K

Description

A team of k (1 <= K <= 100) workers should paint a fence which contains N (1 <= N <= 16 000) planks numbered from 1 to N from left to right. Each worker i (1 <= i <= K) should sit in front of the plank Si and he may paint only a compact interval (this means that the planks from the interval should be consecutive). This interval should contain the Si plank. Also a worker should not paint more than Li planks and for each painted plank he should receive Pi $ (1 <= Pi <= 10 000). A plank should be painted by no more than one worker. All the numbers Si should be distinct.

Being the team's leader you want to determine for each worker the interval that he should paint, knowing that the total income should be maximal. The total income represents the sum of the workers personal income.

Write a program that determines the total maximal income obtained by the K workers.

Input

The input contains:
Input
N K
L1 P1 S1
L2 P2 S2
...
LK PK SK
Signification
N -the number of the planks; K -the number of the workers
Li -the maximal number of planks that can be painted by worker i
Pi -the sum received by worker i for a painted plank
Si -the plank in front of which sits the worker i

Output

The output contains a single integer, the total maximal income.

Sample Input

8 4
3 2 2
3 2 3
3 3 5
1 1 7 

Sample Output

17

Hint

Explanation of the sample:

the worker 1 paints the interval [1, 2];

the worker 2 paints the interval [3, 4];

the worker 3 paints the interval [5, 7];

the worker 4 does not paint any plank

Source

Romania OI 2002

Solution:

本题是单调队列维护 DP 的好题。

首先对油漆工按位置 S[] 排序

令 dp[i][j] 表示前 i 个油漆工涂前 j 块木板(部分可以不涂)的最大收益,则

  • dp[ i ][ j ] = max{ dp[ i ][ j - 1 ], dp[ i - 1 ][ j ], dp[ i - 1 ][ k ] + p[ i ] * ( j - k ) }
  • max 中的第一项表示第 j 块木板不涂;
  • 第二项表示第 i 个油漆工不工作;
  • 第三项表示前 i - 1 个油漆工涂了前 k 块,第 i 个涂了 j - k 块,那么
    • j 的取值范围为 [ Si, Si + Li ) …… (1)
    • k 的取值范围为 [ j - Li, min{ j, Si } ) …… (2)

如果直接枚举 k 来转移,总时间复杂度可达 O(KN2),TLE。

我们发现,复杂度的瓶颈就是第三项中寻找 k 的 O(N) 算法。

第三项可以化为 (dp[ i - 1 ][ k ] + p[ i ] *  k) + p[ i ] *  j

而 p[ i ] * j 在枚举 i, j 之后就已经固定,只需求出使得 dp[ i - 1 ][ k ] + p[ i ] *  k 最大的 k 即可。

由 (2) 式可得,当 j 增大时,k 的上下界均单调递增。这符合单调队列的要求。

所以可以用单调队列维护 k 值,寻找 k 的复杂度降为 O(1),总复杂度降为 O(KN),可以 AC。

这道题我倒是没有 TLE,反而 WA 了数次。究其原因,首先是对单调队列要求的疏忽,没有注意维护的值必须是静态不变的,本题中单调队列维护的值 dp[ i - 1 ][ k ] + p[ i ] *  k 与 j 无关。

其次是思路不明确,没有注意只有第三项对 j 的取值范围有要求,而前两项在整个区间 j ∈ [1, N] 上均可转移

单调队列的题还是要多做做。。

Code: O(KN) [7588K, 219MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int N, K;
int dp[110][16010];
int q[16010], fr, re;

struct Worker{
	int L, P, S;
	
	inline bool operator < (const Worker &w2) const {return S < w2.S;}
} w[110];

int main(){
	scanf("%d%d", &N, &K);
	for(register int i = 1; i <= K; i++) scanf("%d%d%d", &w[i].L, &w[i].P, &w[i].S);
	sort(w + 1, w + K + 1);
	memset(dp, 0, sizeof(dp));
	for(register int i = 1; i <= K; i++){
		fr = re = 0, q[re++] = max(w[i].S - w[i].L, 0);
		for(register int j = 1; j <= N; j++){
			dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);  // This transformation must be done !!!!!!
			if(j < w[i].S || j >= w[i].S + w[i].L) continue;
			int lb = j - w[i].L, ub = min(j, w[i].S) - 1;
			#define calc(x) (dp[i - 1][x] - w[i].P * (x))
			// Maintain the monotone queue using a j-uncorrelated method !!!
			while(q[re - 1] + 1 <= ub){
				int cur = q[re - 1] + 1;
				while(fr != re && calc(cur) >= calc(q[re - 1])) re--;
				q[re++] = cur;
			}
			while(fr != re && q[fr] < lb) fr++;
			if(fr != re) dp[i][j] = max(dp[i][j], calc(q[fr]) + w[i].P * j);
		}
	}
	printf("%d\n", dp[K][N]);
	return 0;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai