题目链接：http://poj.org/problem?id=1821

题意

有$K$个工人刷木板，木板从左到右编号为$1－N$，构成一个从$1$到$N$的序列。

第$i$个工人可以刷也可以不刷，刷的话必须连续的长度不超过$Li$的一段，且必须包含第$Si$块，他每刷一块收益为$Pi$。

每一块木板只能被一个工人刷。

总收益就是所有工人个人收益的和。

求最大总收益。

数据范围：$1 <= N <= 16000, 1 <= K <= 100, Pi <= 10000$。

分析&做法

结合数据范围可知这显然这是一道序列DP问题。

但是需要转化一下，工人的顺序是无序的，我们按照工人的$Si$从小到大对他们拍一下序就好了。

设$f[i][j]$表示前$i$个工人刷前$j$块木板（前$j$块木板可以有空着不刷的）的最大收益。

转移分为三种情况：

1. 第$i$个工人什么也不做，直接由上一个人转移过来就好了：$f[i][j] = f[i - 1][j]$。
2. 第$i$个工人不刷第$j$个格子，空过去不刷，那么可以由上一块木板转移过来：$f[i][j] = f[i][j - 1]$。
3. 第$i$个工人刷第$k + 1$到第$j$块木板，此时枚举$k$进行转移：$f[i][j] = max(f[i][j], f[i - 1][k] + Pi * (j - k))$，其中$j - Li <= k <= Si - 1$。

这种做法的时间复杂度显然是$O(N^2K)$的，超时过不了。

（此处留坑，单调队列式子写起来有些麻烦，我得先去做作业......）

代码

$O(N^2K)$做法：

#include 
#include 
#include 
#include 
#define Re register
using namespace std;

const int maxN = 16005, maxK = 105;

int N, K, f[maxK][maxN], Ans;

struct Workers { int S, P, L; } a[maxK];

bool cmp(Workers x, Workers y) {
    return x.S < y.S;
}

int main() {
    scanf("%d%d", &N, &K);
    for (int i = 1; i <= K; ++i)
        scanf("%d%d%d", &a[i].L, &a[i].P, &a[i].S);        
        
    sort(a + 1, a + K + 1, cmp);    
    
    for (Re int i = 1; i <= K; ++i) {
        for (Re int j = 1; j <= N; ++j) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (j >= a[i].S && j - a[i].S < a[i].L) {
                for (Re int k = max(0, j - a[i].L); k < a[i].S; ++k)
                    f[i][j] = max(f[i][j], f[i - 1][k] + a[i].P * (j - k));                    
            }
        }        
    }
    printf("%d\n", f[K][N]);
    return 0;
} 

$O(NK)$做法（AC代码）

#include 
#include 
#define Re register
using namespace std;

const int maxN = 16005, maxK = 105;

int N, K, f[maxK][maxN], g[maxN];

struct Workers { int S, P, L; } a[maxK];

bool cmp(Workers x, Workers y) {
    return x.S < y.S;
}
int q[maxN << 1], head, tail;
inline int calc(int i, int k) {
    return f[i - 1][k] - a[i].P * k;
}
int main() {
    scanf("%d%d", &N, &K);
    for (int i = 1; i <= K; ++i)
        scanf("%d%d%d", &a[i].L, &a[i].P, &a[i].S);        
        
    sort(a + 1, a + K + 1, cmp);    
    
    for (Re int i = 1; i <= K; ++i) {
        Re int head = 1, tail = 0;
        for (Re int k = max(0, a[i].S-a[i].L); k < a[i].S; ++k) {
            while (head <= tail && calc(i, k) >= calc(i, q[tail])) --tail;
            q[++tail] = k;        
        }        
        for (Re int j = 1; j <= N; ++j) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (j >= a[i].S && j - a[i].S < a[i].L) {
                while (head <= tail && j - q[head] > a[i].L) ++head;
                    f[i][j] = max(f[i][j], calc(i, q[head]) + a[i].P * j);
            }
        }        
    }
    printf("%d\n", f[K][N]);
    return 0;
}