chores专题

(POJ 1949)Chores DAG简单DP

Chores Time Limit: 3000MS Memory Limit: 30000K Total Submissions: 6129 Accepted: 2881 Description Farmer John’s family pitches in with the chores during milking, doing all the chores as quickly as

poj 1949 Chores

题意是有N行任务,给出完成每项任务所需要的时间长度,求出完成所有任务所需要的最短时间.每个任务都会有一个约束条件,就是在完成这项任务之前必须完成所列出的其它任务.可以同时做多项任务.简单来说就像煮饭炒菜问题一样,可以一边烧饭一边炒菜.但炒菜之前必先洗菜.不要想太复杂了,杂活i所需要的时间是本身的时间加上完成前提杂活的最晚时间。完成杂活的总时间就是各个杂活完成的最大时间。#include<std