题解：P13898 [CSPro 28] 训练计划

· · 题解

题目传送门

计算每个科目的最早开始时间和最晚开始时间。依赖关系要求一个科目必须在它所依赖的科目完成后才能开始。

问题要求计算每个科目的最早和最晚开始时间。依赖关系是树形结构，且科目编号有序。

最早开始时间：对于每个科目，如果没有依赖 (p_i=0)，最早开始时间为 1；否则，最早开始时间为依赖科目的最早开始时间加上依赖科目的耗时，也就是依赖科目的结束时间 +1。

最晚开始时间：需要逆向处理。首先检查所有科目是否能在 n 天内完成。如果不能，则只输出最早开始时间；否则，计算最晚开始时间。

对于最晚开始时间，考虑依赖关系：一个科目的延迟会影响所有依赖它的科目。因此需要从后向前处理。对于科目 i，如果没有其他科目依赖它，那么它的最晚开始时间是 n-t_i+1；否则，它的最晚开始时间应取所有依赖它的科目的最晚开始时间减去 t_i 的最小值，保证依赖它的科目能按时开始。

整理成步骤：

  1. 计算最早开始时间：使用动态规划从前向后处理，因为每个科目的依赖科目编号小于自己。
  2. 检查可行性：计算每个科目的最早结束时间，如果所有结束时间 \le n，则可行。
  3. 计算最晚开始时间：使用逆向动态规划。对于每个科目 i，计算所有依赖它的科目 j 的最晚开始时间减去 t_i（因为科目 i 必须在科目 j 开始前完成）的最小值。

CODE：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e2+5;
int n,m,p[N],t[N],ea[N],la[N],chi[N][N],cnt[N];
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>p[i];
    for(int i=1;i<=m;i++)
        cin>>t[i];
    for(int i=1;i<=m;i++)
        if(p[i]==0)
            ea[i]=1;
        else
            ea[i]=ea[p[i]]+t[p[i]];
    bool f=true;
    for(int i=1;i<=m;i++)
        if(ea[i]+t[i]-1>n){
            f=false;
            break;
        }
    for(int i=1;i<=m;i++)
        cout<<ea[i]<<" ";
    cout<<endl;
    if(!f)
        return 0;
    for(int i=1;i<=m;i++)
        if(p[i]!=0)
            chi[p[i]][cnt[p[i]]++]=i;
    for(int i=m;i>=1;i--)
        if(cnt[i]==0)
            la[i]=n-t[i]+1;
        else{
            int minx=1e9;
            for(int j=0;j<cnt[i];j++)
                if(la[chi[i][j]]-t[i]<minx)minx=la[chi[i][j]]-t[i];
            la[i]=minx;
        }
    for(int i=1;i<=m;i++)
        cout<<la[i]<<" ";
    return 0;
}