(動态規劃 + 單調隊列優化)圍欄

題目連結：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;
}