AcWing 298. 围栏

题目描述

有N块木板从左到右排成一行,有M个工匠对这些木板进行粉刷,每块木板至多被粉刷一次。

第 i 个木匠要么不粉刷,要么粉刷包含木板 $S_i$ 的,长度不超过 $L_i$ 的连续的一段木板,每粉刷一块可以得到 $P_i$ 的报酬。

不同工匠的$S_i$不同。

请问如何安排能使工匠们获得的总报酬最多。

输入格式

第一行包含两个整数N和M。

接下来M行,每行包含三个整数$L_i,P_i,S_i$。

输出格式

输出一个整数,表示结果。

数据范围

$1 \le N \le 16000$,
$1 \le M \le 100$,
$1 \le P_i \le 10000$

输入样例:

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

输出样例:

1
17

解题报告

题意理解

一个区间的木块要粉刷,每一个木块最多只能粉刷一次,可以不粉刷,对于一个粉刷匠$i$而言,他必须粉刷第$S_i$木板,而且只能粉刷一段连续的木块,并且要求粉刷长度不超过$L_i$,而且每刷一个木板,就可以得到$P_i$的报酬,现在要求报酬最大化,


解题思路

①首先将所有粉刷匠,按照必须刷的小木块$S_i$从小到大排序.

上面这个操作为了保证我们可以顺序处理.

②我们可以设$f[i][j]$表示为,前$i$个粉刷匠,刷了前$i$个木块.可以有些木块选择不刷

状态确定好了后,我们分两种情况讨论.

  1. 第$i$个粉刷匠不工作,那么
    $$
    f[i][j]=f[i-1][j]
    $$

  2. 第$j$个木板不刷,那么
    $$
    f[i][j]=f[i][j-1]
    $$
    .

结合上面的讨论,我们不难发现,
$$
f[i][j]=max(f[i-1][j],f[i][j-1])
$$


接下来的问题就是,如果说粉刷匠工作,而且也还刷第$j$个木块,那么我们不得不仔细思考.

对于一个粉刷匠而言,如果说聘请他工作,那么显然我们有几个条件.

  1. 他粉刷的区间长度,至少为$1$,最多为$L_i$.
  2. 他粉刷的区间内必须包括$S_i$这个小木块.
  3. 粉刷区间左端点,必须小于等于$S_i$

综上所述我们不妨设置一个粉刷匠粉刷的区域为$[k+1,j]$

那么根据上面所说的条件,我们将它转换为数学计算机语言,如下面这个式子所示.
$$
k+1 \le s_i \le j \
1 \le j-(k+1) \le L_i \
K \le S_i-1
$$


综上所述,我们可以将状态转移方程一步步出来.

$$
f[i][j]=\max{f[i-1][j],f[i][j-1],f[i][j]} \
f[i][j]=\max_{j-L_i \le k \le S_i-1} (f[i][j],f[i-1][k]+P_i*(j-(k+1)+1)) \
$$

得出了一个朴素的状态转移方程,我们不得不进行转换一下.

$$
f[i][j]=\max_{j-L_i \le k \le S_i-1} (f[i][j],f[i-1][k]+P_i*(j-(k+1)+1)) \
$$

我们不妨去掉一个括号.

$$
f[i][j]=\max_{j-L_i \le k \le S_i-1} (f[i][j],f[i-1][k]+P_i*(j-k)) \
$$

123.png


上面的一次次变换,让我们发现了,如果说我们要求的$f[i][j]$要选取到最大值,那么我们核心目标点就是让Max函数内部的

$$
f[i-1][k]-P_i*k
$$

尽量地大.

尽然如此的话,我们发现K的取值是一个范围,但是我们并不关心这个范围内所有的数值,我们唯一的关心点就是这个范围的最大值.也就是最大的$f[i-1][k]$

一个区间,最大值,这些关键字眼,不得不让我们思考一下单调队列这种优秀的数据结构.因此我们把中心放到单调队列上面.


单调队列的核心要点,就是生存能力的判断.

我们逐步入手,下面给出几个判断依据.

我们设当前有两个点,一个是$k_1$,另外一个是$k_2$.

我们发现当前点,如果说$k_1<k_2$,也就是$k_2$后出现.

我们将$k_1$,$k_2$代入到我们的状态转移方程中的决定部分.

那么将$k_1$代入

$
f[i-1][k_1]-P_i * k_1
$

再将$k_2$代入其中

$
f[i-1][k_2]-P_i * k_2
$

我们发现如果说我们再满足下面这个条件的话,那么$k_2$一定优于$k_1$

1234.png

就好比如说,一个人比你小,还比你强,那么你就真的比不过他了.


代码分析

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
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
const int M=16000+100;
const int N=110;
int n,m,i,j,k,f[N][M];
struct node
{
int p,l,s;//单价;最高长度;必备点
} a[M];
deque<int> q;
int cmp(node a,node b)//排序
{
return a.s<b.s;
}
void init()
{
ios::sync_with_stdio(false);
cin>>m>>n;
for(int i=1;i<=n;i++)
cin>>a[i].l>>a[i].p>>a[i].s;
sort(a+1,a+1+n,cmp);
}
int date(int i,int k)
{
return f[i-1][k]-a[i].p*k;
}
void work()
{
for(int i=1;i<=n;i++)//粉刷匠
{
for(int k=max(0,a[i].s-a[i].l);k<a[i].s;k++)
{
while (q.size() && date(i,q.back())<=date(i,k))//不是最优值
q.pop_back();
q.push_back(k);
}
for(int j=1;j<=m;j++)//粉刷墙
{
f[i][j]=max(f[i-1][j],f[i][j-1]);//第一步取最大值
if (j>=a[i].s)
{
while(q.size() && q.front()<j-a[i].l)//不在候选范围内了.
q.pop_front();
if (q.size())
f[i][j]=max(f[i][j],a[i].p*j+date(i,q.front()));//计算
}
}
}
cout<<f[n][m];
}
int main()
{
init();
work();
return 0;
}