算法标签

$动态规划、最优决策选择$

解题思路

题意分析

题目描述了一个关于车辆运送的场景。已知有$n$个停车场（可理解为一次能运送的车辆数量上限），每辆车从出发到返回的时间间隔为$t$（包含去程和回程时间），总共有$m$辆车需要运送，并且给出了每辆车的到达时间序列$f[i]$（$i$从$1$到$m$）。目标是确定最后一辆车被送到的最早时间以及在送完最后一辆车时总共运送的次数。在运送车辆的过程中，每次运送的车辆数量不能超过$n$，且要根据车辆的到达时间合理安排运送计划，以达到最后一辆车最早送达的目的。

解题思路

1. 数据初始化与输入处理：
   • 定义了一些常量，如maxn表示数组的最大长度，inf表示一个很大的数用于初始化最小值。
   • 定义了三个数组dp[i]表示第$i$辆车被送到的最早时间，si[i]表示第$i$辆车被送到时已经送过的次数，f[i]用于存储每辆车的到达时间。
   • 输入测试用例的数量$T$，对于每个测试用例，输入停车场数量$n$、每辆车往返时间$t$、车辆总数$m$，以及每辆车的到达时间$f[i]$。
2. 动态规划计算：
   • 外层循环遍历每一辆车（从第$1$辆车到第$m$辆车）。
   • 对于每一辆车$i$，通过内层循环从$i - 1$到$\max(0, i - n)$来寻找之前的某一次运送，使得当前车$i$能最早被送达。这里寻找的依据是比较之前各次运送完成的时间dp[j]（$j$为之前的某次运送），找到最小的dp[j]对应的$j$值（设为mj）。
   • 如果mj小于等于$0$，则将mj设为$1$。
   • 计算第$i$辆车被送到的最早时间dp[i]，其值为$\max(dp[mj - 1], f[i]) + t \times 2$。这里的$\max(dp[mj - 1], f[i])$表示要等之前的运送完成以及当前车到达，然后再加上往返时间$t \times 2$。
   • 计算第$i$辆车被送到时已经送过的次数si[i]，其值为si[mj - 1] + 1，即在上一次运送次数的基础上加$1$。
3. 结果输出：
   • 最后输出第$m$辆车被送到的最早时间（dp[m] - t，减去$t$是因为dp[m]包含了最后一次的往返时间，这里只需要到达时间）以及送完第$m$辆车时总共运送的次数si[m]。

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=100000;
const int inf=10000000;
int dp[maxn];///第i辆车被送到的最早时间
int si[maxn];///第i辆车被送到时已经送过的次数
int f[maxn];
int main() {
    int T; cin>>T;
    while(T--) {
        int n,t,m; cin>>n>>t>>m;
        for(int i=1; i<=m; ++i)cin>>f[i];
        for(int i=1;i<=m;++i){
            int min=inf,mj;
            for(int j=i-1;j>=0&&j>i-n;--j)
                if(dp[j]<=min)
                    min=dp[j],mj=j;
            if(mj<=0) mj=1;
            dp[i]=max(dp[mj-1],f[i])+t*2;
            si[i]=si[mj-1]+1;
        }
        cout<<dp[m]-t<<' '<<si[m]<<endl;
    }
    return 0;
}