题解：最大化工钱问题

题目分析

这道题目给定了 K 个人，每个人最多能涂一段连续的木板，涂木板的工钱为每块木板的工钱乘上它的位置。每个人只能涂包含自己站的位置的区间长度为 l 的木板，而每个人最多能涂的木板数也是有限的。求最大化这些工钱的和，且每个人涂的区间不能重叠，且每个人最多涂的木板数为 l。

关键思路

1. 动态规划的构建：

   • 我们定义 dp[i][j] 表示前 i 个人涂完前 j 块木板的最大工钱。
   • 状态转移主要包括三种情况：
     1. 当前木板不涂：dp[i][j] = dp[i][j-1]，即第 i 个人不涂第 j 块木板，工钱没有增加。
     2. 当前人不涂任何木板：dp[i][j] = dp[i-1][j]，即第 i 个人不涂任何木板，工钱没有增加。
     3. 当前人涂某个区间的木板：如果第 i 个人涂第 j 个木板，且涂的区间合法，则工钱为 j * p_i 加上前 i-1 个人涂前某个合法区间的最大工钱。

2. 优化：

   • 使用单调队列来优化状态转移，避免暴力枚举所有可能的区间。单调队列保证了 dp[i][j] 的转移是线性的，从而减少了计算复杂度。

动态规划状态转移方程

• 初始化：dp[0][0] = 0，表示没有人涂任何木板时工钱为 0。
• 状态转移：
  • dp[i][j] = max(dp[i][j-1], dp[i-1][j])，如果第 i 个人不涂第 j 个木板。
  • dp[i][j] = max(dp[i][j], j * p_i + max(dp[i-1][k] - k * p_i))，其中 k 满足 j - l_i <= k <= s_i - 1。

代码实现

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 16005;

int n, k, dp[105][maxn], h, t;

struct Node {
    int l, p, s;
    bool operator<(const Node &a) const {
        return s < a.s;
    }
} node[105];

struct Q {
    int val, id;
    Q() {}
    Q(int x, int y) { val = x; id = y; }
} q[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;

    for (int i = 1; i <= k; ++i) {
        cin >> node[i].l >> node[i].p >> node[i].s;
    }

    sort(node + 1, node + 1 + k);

    for (int i = 1; i <= k; ++i) {
        h = 1; t = 0;

        // 入队
        for (int j = max(0, node[i].s - node[i].l); j <= node[i].s - 1; ++j) {
            Q tmp(dp[i-1][j] - j * node[i].p, j);
            while (h <= t && q[t].val <= tmp.val) t--;
            q[++t] = tmp;
        }

        for (int j = 1; j <= n; ++j) {
            dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
            if (j >= node[i].s) {
                // 排除队头不合法决策
                while (h <= t && q[h].id < j - node[i].l) h++;

                if (h <= t)
                    dp[i][j] = max(dp[i][j], j * node[i].p + q[h].val);
            }
        }
    }

    cout << dp[k][n];
    return 0;
}

代码解析

1. 输入解析：输入的每一项都包含每个人的最大涂板数、工钱和站的位置，我们将这些数据存储在 node 数组中。

2. 动态规划初始化：

   • 我们初始化 dp[0][0] = 0，表示没有人涂任何木板时工钱为 0。
   • 每个 dp[i][j] 表示前 i 个人涂完前 j 个木板的最大工钱。

3. 单调队列优化：

   • 使用单调队列来优化 dp[i][j] 的计算，确保每次选择的区间是合法的，并且通过单调队列快速获得最大值，从而减少了计算复杂度。

4. 结果输出：最终输出 dp[k][n]，即前 k 个人涂完 n 块木板后的最大工钱。

时间复杂度分析

• 时间复杂度：每次计算 dp[i][j] 时，需要检查前 j 个木板的情况，且使用单调队列进行优化，时间复杂度为 O(N * M)，其中 N 为木板数，M 为最多的人数，因此整体时间复杂度为 O(N * M)。

总结

这道题的关键在于状态转移的设计，利用动态规划和单调队列优化状态转移，能够有效求解最大化工钱的问题。通过合理的状态定义和优化，能够处理大规模的输入数据。