Input
Output
Sample Input
7 5 0 1 1 1 3 1 2 6 1 1 1 2 2 4 8 2 2 4 4 3 3 5 6
Sample Output
23
Hint
[Here is one task schedule:
Chore 1 starts at time 0, ends at time 5.
Chore 2 starts at time 5, ends at time 6.
Chore 3 starts at time 6, ends at time 9.
Chore 4 starts at time 5, ends at time 11.
Chore 5 starts at time 11, ends at time 12.
Chore 6 starts at time 11, ends at time 19.
Chore 7 starts at time 19, ends at time 23.
]
题解：树形DP入门题。从根节点往下依次更新出每一个节点的最短时间，则该最短时间的最大值即为：完成家务的最短时间。
参考代码为：
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=10005;
int c[maxn],n[maxn],dp[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int N,temp,sum=-maxn;
memset(dp,0,sizeof dp);
cin>>N;
for(int i=1;i<=N;i++)
{
cin>>c[i]>>n[i];
if(i==1) dp[i]=c[i];
else
{
int max=-maxn;
if(n[i]==0) dp[i]=c[i];
else
{
for(int j=0;j<n[i];j++)
{
cin>>temp;
if(dp[temp]>max) max=dp[temp];
}
dp[i]=max+c[i];
}
}
if(dp[i]>sum) sum=dp[i];
}
cout<<sum<<endl;
return 0;
}
/*
7
5 0
1 1 1
3 1 2
6 1 1
1 2 2 4
8 2 2 4
4 3 3 5 6
*/
原文：https://www.cnblogs.com/songorz/p/9409663.html