(动态规划 + 单调队列优化)围栏

题目链接：https://www.acwing.com/problem/content/description/300/

参考文献：

文献1：https://www.acwing.com/solution/content/2130/

文献2:https://www.acwing.com/solution/content/6676/

题目：

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

第 i 个木匠要么不粉刷，要么粉刷包含木板 Si 的，长度不超过 Li 的连续的一段木板，每粉刷一块可以得到 Pi 的报酬。

不同工匠的 Si 不同。

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

输入格式

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

接下来 M 行，每行包含三个整数 Li,Pi,Si。

输出格式

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

数据范围

1≤N≤16000,

1≤M≤100,

1≤Pi≤10000

输入样例：

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

输出样例：

17
           

 分析：动态规划

f[i][j]状态表示： 从前i个人中选，去涂前j个木板（不一定所有木板都要涂）。

状态计算：

1.不选择第i个人： f[i - 1][j];

2.不涂第j个木: f[i][j - 1]

3.选第i个人并且涂第j个木块:

而最难的便是对第三种状态进行分析：

根据第三种状态和题意可得一些条件：

(1）即然选择了第i个人，第i个人就一定要涂s[i];

(2) 第j个木块必须涂，并且由于我们会对s进行排序，所以第j个木块必定是第i个人涂

(3)由（1），（2）可以知道第i个人所涂木块的范围：

j - L + 1  ~ j  -》 s[i] ~ j

(4)第三种要i且涂j的为：f[i][j] = ff[i - 1][k] + (j - k) * p.  // 举例：如k = 1, 则 第i个涂，2 ~j共 j - 1个木块，然后 * p.

(5)k的取值范围： 0<= k <= s[i] - 1.  因为 第i个人至少涂k + 1 并且要涂s[i]

(6)

 (7)而随着j的不断增大， k的上界 si - 1 不变， k的下界 j - Li则不断变小。 所以区间不断变小。 求一个区间中

 如果用暴力的做法，每遍历一次j，我们都要从j - Li~ si - 1的去遍历k.

实际上我们可以知道，如果 k1 < k2 

且 f[i - 1][k1] - pi * k1 < f[i - 1][k2] - pi * k2 的话，

所以当j不断的增加的时候， j - Li不断的减小，所以k1最先不满足条件，而且当k1,k2都满足条件时，只会使用k2的max. 

所以可以使用单调队列进行优化，如果不优化的话，时间复杂度大致为：O(m * n * n == 100 * 16000* 16000 必定超时)

 所以使用单调队列进行优化：

使用单调队列存储  随着j的不断增加，满足条件的k的值存入到队列中。

而k的条件是要 <= s[i] - 1。    所以要想将k加入到单调队列中，k<= s[i] - 1才能满足条件。

而f[i][j]要满足状态计算的第三个情况，则j > = s[i].

所以在遍历for(int j = 0 ; j <= M ; j++)的时候，可以将k和j一并处理， j <= s[i] - 1时用作k处理，加入到单调队列中，j >= s[i] 时则当作第j个木块的含义

 代码实现：

# include <iostream>
# include <algorithm>
using namespace std;
const int N = 16010 , M = 110 ;

struct Node
{
    int s;
    int l;
    int p;
} node[M];

int f[M][N];
int q[N];

int n,m;

bool cmp(struct Node a , struct Node b)
{
    return a.s < b.s;
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 1 ; i <= m ; i++)
    {
        scanf("%d %d %d",&node[i].l,&node[i].p,&node[i].s);
    }
    sort(node + 1, node + m + 1, cmp); //按照s从小到达排序
    
    
    for(int i = 1 ; i <= m ; i++)
    {
        int hh = 0, tt = -1;
        for(int j = 0 ; j <= n ; j++)
        {
            f[i][j] = f[i - 1][j];
            if(j > 0)
            {
                f[i][j] = max(f[i][j],f[i][j - 1]);
            }
            // q[]中存入的都是满足条件的k值,对k值存入到单调队列中
            while(hh <= tt && j - q[hh]> node[i].l)
            {
                hh++;
            }
            if(j >= node[i].s && hh <= tt)
            {
                f[i][j] = max(f[i][j],f[i - 1][ q[hh] ] + (j - q[hh]) * node[i].p);
            }
            if(j < node[i].s) // 只有当j < s[i]的时候，才能够加到f[i - 1][ q[] ]的q[]中，
            {
                while(hh <= tt && f[i - 1][q[tt]] - node[i].p * q[tt] <= f[i - 1][j]  -  node[i].p * j)
                {
                    tt--;
                }
                q[++tt] = j;
            }
        }
    }
    printf("%d\n",f[m][n]);
    return 0;
}