@toc

题目描述

题目链接：here
有$N$块木板从左到右排成一行，有$M$个工匠对这些木板进行粉刷，每块木板至多被粉刷一次。
第$i$个木匠要么不粉刷，要么粉刷包含木板$Si$的，长度不超过$Li$的连续的一段木
板，每粉刷一块可以得到$Pi$的报酬。
不同工匠的$Si$不同。
请问如何安排能使工匠们获得的总报酬最多。
$1\le N\le 16000$
$1\le M\le 100$
$1\le Pi\le 10000$

样例

in:
8 4
3 2 2
3 2 3
3 3 5
1 1 7 
30 10
5 6 17
5 21 24
4 15 15
5 4 10
5 11 2
4 15 13
6 14 8
1 11 23
5 8 21
6 8 30
out:
17
412

算法1: 单调队列优化DP

这个做法网上太多题解了，写的都挺好，推荐两篇别人的题解吧。
时间复杂度: $O(nm)$
参考文献：whsstory,心里没有一点AC数

C++ AC 代码

运行时间：57ms

int n, m;
int L[105], P[105], S[105], d[MXN];
int dp[105][MXN], Q[MXN], hd, tl;
int main() {
#ifndef ONLINE_JUDGE
    freopen("D:in.in", "r", stdin);
    freopen("D:out.out", "w", stdout);
#endif
    n = read(), m = read();
    for(int i = 1; i <= m; ++i) {
        L[i] = min((int)read(), n);
        P[i] = read();
        S[i] = read();
        d[i] = i;
    }
    sort(d + 1, d + m + 1, [](const int &x, const int &y){return S[x] < S[y];});
    for(int ti = 1, i, i1; ti <= m; ++ ti) {
        i = d[ti];
        i1 = d[ti-1];
        hd = tl = 1;
        for(int j = max(0, S[i] - L[i]); j < S[i]; ++j) {
            while(hd < tl && dp[i1][Q[tl-1]] - P[i] * Q[tl-1] <= dp[i1][j] - P[i] * j) {
                -- tl;
            }
            Q[tl ++] = j;
        }
        for(int j = 1; j <= n; ++j) {
            dp[i][j] = max(dp[i1][j], dp[i][j-1]);
            if(j >= S[i]) {
                while(hd < tl && Q[hd] < j - L[i]) ++ hd;
                if(hd < tl) dp[i][j] = max(dp[i][j], dp[i1][Q[hd]] + P[i] * (j - Q[hd]));
            }
        }
        // debug(hd, tl)
        // assert(hd == tl);
    }
    for(int i = 1; i <= n; ++i) dp[d[m]][0] = max(dp[d[m]][0], dp[d[m]][i]);
    printf("%d\n", dp[d[m]][0]);
    return 0;
}

算法2: 直接DP

思路

$g[i]$表示前$i$块木板粉刷的最大收益
$h[j][i]$表示第$j$个工匠从第$S[j]$块木板开始向左至多粉刷$i$块木板的最大收益，当然第$S[j]$块木板是必刷的呀
状态转移：

• 当$i>S[j]\;and\;i - S[j] + 1 <= L[j]:$
  $g[i] = max(g[i], h[j][L[j]-(i-S[j]+1)] + P[j] * (i - S[j]))$

• 当$i == S[j]:$
  维护$h[j][k]$数组：$h[j][k] = max(g[i - x - 1] + (x + 1) * P[j]), 0\le x\le k$
  $g[i] = h[j][L[j]]$

答案是：$g[n]$
时间复杂度: $O(nm)$
思路来源：火星鼠

C++ AC 代码

运行时间：36ms

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;int f = 0;char ch = getchar();
    while (ch < '0' || ch > '9') f |= (ch == '-'), ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch =
    getchar(); return x = f ? -x : x;
}
void debug_out() { cout << '\n'; }
template <typename T, typename... R>
void debug_out(const T &f, const R &... r) {
    cout << f << " ";
    debug_out(r...);
}
#define debug(...) cout << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__);
const int MXN = 2e4 + 5;
int n, m;
int L[105], P[105], S[105];
// int f[MXN];
int g[MXN], h[105][MXN];
int main() {
#ifndef ONLINE_JUDGE
    freopen("D:in.in", "r", stdin);
    freopen("D:out.out", "w", stdout);
#endif
    n = read(), m = read();
    for(int i = 1; i <= m; ++i) {
        L[i] = min(read(), n);
        P[i] = read();
        S[i] = read();
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(L[j] == 0) continue;
            if(i > S[j] && i - S[j] + 1 <= L[j])
                g[i] = max(g[i], h[j][L[j]-(i-S[j]+1)] + P[j] * (i - S[j]));
            else if(i == S[j]) {
                int tmp = 0, k = 0;
                for(; k <= i - 1 && k + 1 <= L[j]; ++ k) {
                    tmp = max(g[i - k - 1] + (k + 1) * P[j], tmp);
                    h[j][k] = tmp;
                }
                for(; k <= L[j]; ++k) h[j][k] = max(h[j][k-1], h[j][k]);
                g[i] = max(g[i], tmp);
            }
            // else if(i < S[j] && S[j] - i + 1 <= L[j]) 
                // f[i] = max(f[i], g[i-1] + P[j]);
        }
        // debug(i, f[i])
        g[i] = max(g[i-1], g[i]);
    }
    printf("%d\n", g[n]);
#ifndef ONLINE_JUDGE
    // cout << "time cost:" << 1.0 * clock() / CLOCKS_PER_SEC << "ms" << endl;
    // system("pause");
#endif
    return 0;
}

算法3: 线段树维护DP

补了再填上
时间复杂度: $O(nmlog(n))$