题目链接
这道题是很经典的一道维护单调队列的题目，最近在做POJ的题目。记录一下这道题。
题意是$K$个工人，$N$个木板。每个工人可以最多涂$L_i$个木板，涂木板的区间必须是连续的，且必须包含$S_i$位置的木板，涂每块木板的收入是$P_i$，求这些工人最多的收入是多少。
DP。DP[i][j]表示i个工人涂j个木板的最多收入。则有
$DP[i][j] = max(dp[i-1][j],dp[i][j-1], dp[i-1][k] + peo[i].pay*(j-k))$
这里 $dp[i-1][k] + peo[i].pay*(j-k))$表示前面$i-1$个人涂了$k$个木板，第$i$个工人涂接下来的$j-k$个。
会发现此时$dp[i-1][k] + peo[i].pay*(j-k)) = dp[i-1][k] - peo[i].pay*k+ peo[i].pay*j$ 。前面的$ dp[i-1][k] - peo[i].pay*k$可以采用单调队列解决。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| int n,k;
struct po {
int len;
int st;
int pay;
}peo[200];
bool cmp(po p1,po p2) {
return p1.st < p2.st;
}
int dp[105][17000];
deque<int>q;
void solve() {
sa(n),sa(k);
repp(i,1,k) {
sa(peo[i].len);
sa(peo[i].pay);
sa(peo[i].st);
}
sort(peo+1,peo+k+1,cmp);
repp(i,1,k) {
q.push_front(max(0,peo[i].st-peo[i].len));
repp(j,1,n) {
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
if(j >= peo[i].st + peo[i].len)continue;
while(!q.empty() && q.front() + peo[i].len < j)
q.pop_front();
if(j < peo[i].st) {
int t = dp[i-1][j] - peo[i].pay*j;
while(!q.empty() && dp[i-1][q.back()] - peo[i].pay*q.back()< t)
q.pop_back();
q.push_back(j);
continue;
}
int ans = 0;
if(!q.empty())
ans = dp[i-1][q.front()] + peo[i].pay*(j-q.front());
dp[i][j] = max(dp[i][j],ans);
}
}
printf("%d\n",dp[k][n]);
}
|