2 shunfurh shunfurh 于 2017.09.17 11:31 提问

Chores

Description

Farmer John's family pitches in with the chores during milking, doing all the chores as quickly as possible. At FJ's house, some chores cannot be started until others have been completed, e.g., it is impossible to wash the cows until they are in the stalls.

Farmer John has a list of N (3 <= N <= 10,000) chores that must be completed. Each chore requires an integer time (1 <= length of time <= 100) to complete and there may be other chores that must be completed before this chore is started. We will call these prerequisite chores. At least one chore has no prerequisite: the very first one, number 1. Farmer John's list of chores is nicely ordered, and chore K (K > 1) can have only chores 1,.K-1 as prerequisites. Write a program that reads a list of chores from 1 to N with associated times and all perquisite chores. Now calculate the shortest time it will take to complete all N chores. Of course, chores that do not depend on each other can be performed simultaneously.
Input

  • Line 1: One integer, N

  • Lines 2..N+1: N lines, each with several space-separated integers. Line 2 contains chore 1; line 3 contains chore 2, and so on. Each line contains the length of time to complete the chore, the number of the prerequisites, Pi, (0 <= Pi <= 100), and the Pi prerequisites (range 1..N, of course).
    Output

A single line with an integer which is the least amount of time required to perform all the chores.
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

1个回答

caozhy
caozhy   Ds   Rxr 2017.10.01 04:15
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
BNU14278 Chores(读懂就能做的水)
Chores Time Limit: 3000ms Memory Limit: 30000KB 64-bit integer IO format: %lld      Java class name: Main Prev Submit Status Statistics Discuss Next Type: None
Educational Codeforces Round 30 A O(n)算法
A. Chores time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Luba has to do n chores today. i-th chore takes ai units
luogu4264 [USACO18FEB]Teleportation S
http://www.elijahqi.win/2018/03/06/luogu4264/ 题目描述 One of the farming chores Farmer John dislikes the most is hauling around lots of cow manure. In order to streamline this process, he comes up wi...
Educational Codeforces Round 30 A. Chore
A. ChoreProblem Statement     Luba has to do n chores today. i-th chore takes ai units of time to complete. It is guaranteed that for every the condition ai ≥ ai - 1 is met, so the sequence is sorte
Chores
Chores 题目链接:http://poj.org/problem?id=1949 Crawling in process...Crawling failedTime Limit:3000MSMemory Limit:30000KB64bit IO Format:%I64d & %I64u SubmitStatus Description Farmer John
DP: Chores
ChoresTime Limit:3000MS    Memory Limit:30000KB    64bit IO Format:%I64d & %I64u SubmitStatusPracticePOJ 1949 Description Farmer John's family pitches in with the chores during milking, d
【usaco2002.4】Chores
#include #include using namespace std; int n,cnt,ans,head[10001],v[10001],r[10001],ed[10001]; struct data{ int to,next; }e[1000001]; void insert(int u,int v){ e[++cnt].to=v; e[cnt].next=head[u]; h
POJ 2376 Cleaning Shifts(贪心,区间问题)
Cleaning Shifts Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 14878 Accepted: 3804 Description Farmer John is assigning some of h
poj1949 chores
/* * poj1949 AC 看起来像拓扑排序的DP * * 关键在于:工作k的前趋在1..k-1进行选择。 * 所以,理解题意可知,令工作i的结束时间为dp[i] * dp[i] = max(dp[j]|工作j为i的前趋)+t[i]; * * 但即使没有此条件,也可以将此题看作是一道树状DP。 * 将拓扑图反向,即将某工作的前趋作为该工作的儿子进行DP。 * 但我的树状DP
usaco2018 feb cu Teleportation
http://www.elijahqi.win/2018/03/03/usaco2018-feb-cu-teleportation/ One of the farming chores Farmer John dislikes the most is hauling around lots of cow manure. In order to streamline this process, ...