poj 1949 Chores

本文主要是介绍poj 1949 Chores，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意是有N行任务,给出完成每项任务所需要的时间长度,求出完成所有任务所需要的最短时间.每个任务都会有一个约束条件,就是在完成这项任务之前必须完成所列出的其它任务.可以同时做多项任务.简单来说就像煮饭炒菜问题一样,可以一边烧饭一边炒菜.但炒菜之前必先洗菜.
不要想太复杂了，杂活i所需要的时间是本身的时间加上完成前提杂活的最晚时间。完成杂活的总时间就是各个杂活完成的最大时间。
#include<stdio.h>
#include<string.h>
int n,time,pre,num,ans,maxn;
int dp[20005];                  
int  main(){
while(scanf("%d",&n)!=EOF)
{
ans=-1;
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
maxn=0;
scanf("%d%d",&time,&pre);
for(int j=1;j<=pre;j++)
{
scanf("%d",&num);
if(dp[num]>maxn)
maxn=dp[num];
}
dp[i]= maxn+time;
if(dp[i]>ans)
ans=dp[i];
}
printf("%d\n",ans);
}
return 0;
}

这篇关于poj 1949 Chores的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---