题目分析

题意简述

有一个懒惰的工人，需要处理一组编号为 $1$ 到 $n$ 的任务。每个任务 $i$ 有其处理时间 $t_i$、到达时间 $a_i$ 和截止时间 $d_i$，且 $t_i$、$a_i$、$d_i$ 均为非负整数。任务具有严格的截止时间，即任务 $i$ 只能在区间 $I_i = [a_i, d_i]$ 内执行。工人一次只能执行一个任务，且任务一旦开始就不能中断。当一个任务完成后，如果有其他可执行的任务，需立即开始执行。若没有可执行任务，工人处于空闲状态，有新任务到达时则马上开始执行。题目要求找出工人执行任务的最小总时间。

输入

• 输入包含 $T$ 个测试用例，$T$ 的值在第一行给出。
• 每个测试用例的第一行是任务数量 $n$（$0 \leq n \leq 100$）。
• 接下来 $n$ 行，每行包含三个整数，分别为任务 $i$ 的处理时间 $t_i$（$1 \leq t_i \leq 20$）、到达时间 $a_i$（$0 \leq a_i \leq 250$）和截止时间 $d_i$（$1 \leq d_i \leq 250$）。

输出

每个测试用例输出一行，包含工人执行任务的最小总时间。

解题思路

动态规划

本题采用动态规划（DP）来解决。设 $dp[tim]$ 表示从时间 $tim$ 开始，工人执行任务的最小总时间。

状态转移

• 边界条件：当 $tim \geq maxi$ 时（$maxi$ 是所有任务截止时间的最大值），$dp[maxi] = 0$，因为此时没有任务可执行。
• 无可用任务情况：如果在时间 $tim$ 没有可执行的任务，即 $v[tim].size() == 0$，则 $dp[tim] = DP(tim + 1)$，也就是直接转移到下一个时间点。
• 有可用任务情况：如果在时间 $tim$ 有可执行的任务，遍历所有可执行任务 $to$，状态转移方程为 $dp[tim] = min(dp[tim], DP(tim + t[to]) + t[to])$，即尝试执行每个可执行任务，取最小的总时间。

预处理

在进行动态规划之前，需要进行一些预处理：

• 找出所有任务截止时间的最大值 $maxi$。
• 对于每个任务 $i$，将其添加到所有满足 $a_i \leq k \leq d_i - t_i$ 的时间点 $k$ 对应的任务列表 $v[k]$ 中，表示在时间点 $k$ 可以开始执行任务 $i$。

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int SIZE = 1280;
int cas,n,maxi;
int t[SIZE],a[SIZE],d[SIZE];
int dp[SIZE<<1];
bool vis[SIZE<<1];
vector <int> v[SIZE<<1];

int DP(int tim)
{
    if(vis[tim])
        return dp[tim];
    if(tim >= maxi)
    {
        dp[maxi] = 0;
        return 0;
    }
    if(v[tim].size() == 0)
        dp[tim] = DP(tim+1);
    else
    {
        for(int i=0; i<(int)v[tim].size(); i++)
        {
            int to = v[tim][i];
            dp[tim] = min(dp[tim],DP(tim+t[to])+t[to]);
        }
    }
    vis[tim] = true;
    return dp[tim];
}

int main()
{
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d",&n);
        for(int i=0; i<256; i++)
            v[i].clear();
        maxi = 0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d%d",&t[i],&a[i],&d[i]);
            for(int k=a[i]; k<=d[i]-t[i]; k++)
                v[k].push_back(i);
            if(d[i] > maxi)
                maxi = d[i];
        }
        for(int i=0; i<SIZE; i++)
            dp[i] = 0xfffffff;
        for(int i=maxi; i<SIZE; i++)
            dp[i] = 0;
        memset(vis,0,sizeof(vis));
        DP(0);
        printf("%d\n",dp[0]);
    }
    return 0;
}    

代码说明

1. 全局变量
   • SIZE：定义数组大小。
   • cas：测试用例数量。
   • n：每个测试用例中的任务数量。
   • maxi：所有任务截止时间的最大值。
   • t[i]：任务 $i$ 的处理时间。
   • a[i]：任务 $i$ 的到达时间。
   • d[i]：任务 $i$ 的截止时间。
   • dp[tim]：从时间 $tim$ 开始，工人执行任务的最小总时间。
   • vis[tim]：标记时间 $tim$ 的状态是否已经计算过。
   • v[tim]：存储在时间 $tim$ 可以开始执行的任务列表。
2. DP 函数
   • DP(int tim)：递归计算从时间 $tim$ 开始的最小总时间。
   • 若 $vis[tim]$ 为 true，说明该状态已经计算过，直接返回 $dp[tim]$。
   • 若 $tim \geq maxi$，则 $dp[maxi] = 0$ 并返回 $0$。
   • 若 $v[tim].size() == 0$，则 $dp[tim] = DP(tim + 1)$。
   • 否则，遍历 $v[tim]$ 中的所有任务，更新 $dp[tim]$ 为最小的 $DP(tim + t[to]) + t[to]$。
   • 最后标记 $vis[tim]$ 为 true 并返回 $dp[tim]$。
3. 主函数
   • 读取测试用例数量 $cas$。
   • 对于每个测试用例：
     • 读取任务数量 $n$。
     • 清空 $v$ 数组。
     • 读取每个任务的处理时间 $t_i$、到达时间 $a_i$ 和截止时间 $d_i$，并将任务添加到相应的时间点列表中。
     • 找出所有任务截止时间的最大值 $maxi$。
     • 初始化 $dp$ 数组，将 $dp[0]$ 到 $dp[maxi - 1]$ 初始化为一个较大的值，$dp[maxi]$ 到 $dp[SIZE - 1]$ 初始化为 $0$。
     • 初始化 $vis$ 数组为 false。
     • 调用 DP(0) 计算从时间 $0$ 开始的最小总时间，并输出 $dp[0]$。