Posted on 2009-08-25 22:21
Uriel 阅读(351)
评论(0) 编辑 收藏 引用 所属分类:
POJ 、
DP
注意，所有Chores是拓扑排序过的，就不算难了。。
不过自己很菜啊。。还是搞了好一会儿
/**//*Problem: 1949 User: Uriel
Memory: 4268K Time: 375MS
Language: C++ Result: Accepted*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int n,i,j,x[10001],dp[10001],p[10001][101],t[10001],ans,MIN[10001];
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d %d",&t[i],&x[i]);
for(j=0;j<x[i];j++)
{
scanf("%d",&p[i][j]);
}
}
for(i=0;i<=n;i++)dp[i]=0;
for(i=1;i<=n;i++)
{
if(x[i]==0)dp[i]+=t[i];
else
{
for(j=0;j<x[i];j++)
{
dp[i]=max(dp[i],dp[p[i][j]]+t[i]);
}
}
}
ans=0;
for(i=1;i<=n;i++)
{
ans=max(ans,dp[i]);
}
printf("%d\n",ans);
system("PAUSE");
return 0;
}