Fence

题目描述

A team of $K$ workers should paint a fence which contains $N$ planks numbered from $1$ to $N$ from left to right. Each worker $i$ should sit in front of the plank $S_i$ and he may paint only a compact interval (this means that the planks from the interval should be consecutive). This interval should contain the $S_i$ plank. Also a worker should not paint more than $L_i$ planks and for each painted plank he should receive $P_i$\$. A plank should be painted by no more than one worker. All the numbers $S_i$ should be distinct.

Being the team’s leader you want to determine for each worker the interval that he should paint, knowing that the total income should be maximal. The total income represents the sum of the workers personal income.

Write a program that determines the total maximal income obtained by the $K$ workers.

题意概述

$K$个工人要粉刷一面长度为$N$的篱笆，第$i$个工人要么不粉刷，要么粉刷一段连续且长度不超过$L_i$的包含第$S_i$块木板的篱笆，他每粉刷一块木板可以获得$P_i$的报酬。每一块木板要么不被粉刷，要么仅被一个工人粉刷。求所有工人获得的总报酬的最大值。

数据范围：$1 \le K \le 100, \ 1 \le N \le 16000$。

算法分析

令$f_{i, j}$表示前$i$个工人粉刷前$j$块木板（不一定全刷）的最大报酬，则可分三种情况讨论：

• 第$i$个工人不粉刷，$f_{i, j}=f_{i-1, j}$；
• 第$j$块木板不被粉刷，$f_{i, j}=f_{i, j-1}$；
• 第$i$个工人粉刷第$(k+1)$到第$j$块木板，$f_{i, j}=f_{i-1, k}+(j-k) \times P_i$。

在第三种情况中，转移方程变形后得$f_{i, j}=(f_{i-1, k}-k \times P_i)+j \times P_i$，$f_{i-1, k}-k \times P_i$与$j$无关，$j \times P_i$与$k$无关，因此对于确定的$i$和$j$，方程后半部分为常数，只要求前半部分的最大值。因为前半部分只与$k$有关，所以可以用单调队列维护其最大值。注意$k$要满足的条件是$k+1 \le S_i \le j$与$j-(k+1)+1 \le L_i$，即$j-L_i \le k \lt S_i$。算法的时间复杂度为$O(KN)$。

代码

#include <cstdio>
#include <algorithm>

int const K = 105, N = 16005;
int f[K][N];
struct Carpenter {
    int l, p, s;
    bool operator < (Carpenter const &t) const {
        return s < t.s;
    }
} c[K];
std::pair<int, int> que[N];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; ++i) {
        scanf("%d%d%d", &c[i].l, &c[i].p, &c[i].s);
    }
    std::sort(c + 1, c + k + 1);
    for (int i = 1; i <= k; ++i) {
        int qb = 0, qe = 0;
        for (int j = 0; j < c[i].s; ++j) {
            for (; qb < qe && que[qe - 1].first <= f[i - 1][j] - c[i].p * j; --qe) ;
            que[qe++] = std::make_pair(f[i - 1][j] - c[i].p * j, j);
        }
        for (int j = 1; j <= n; ++j) {
            f[i][j] = std::max(f[i - 1][j], f[i][j - 1]);
            if (c[i].s <= j && j < c[i].s + c[i].l) {
                for (; qb < qe && que[qb].second < j - c[i].l; ++qb) ;
                f[i][j] = std::max(f[i][j], que[qb].first + c[i].p * j);
            }
        }
    }
    printf("%d\n", f[k][n]);
    return 0;
}