学步园

/*
 * poj1949 AC 看起来像拓扑排序的DP
 * 
 * 关键在于：工作k的前趋在1..k-1进行选择。
 * 所以，理解题意可知，令工作i的结束时间为dp[i]
 * dp[i] = max(dp[j]|工作j为i的前趋)+t[i];
 *
 * 但即使没有此条件，也可以将此题看作是一道树状DP。
 * 将拓扑图反向，即将某工作的前趋作为该工作的儿子进行DP。
 * 但我的树状DP怎么就RE了呢？？？
 *
 * */
#include<cstdio>
#include<algorithm>
#include<memory.h>
using namespace std;

int main()
{
//	FILE* fin;
//	fin = fopen("d.in","r");
	long ans = 0,over[10010];
	int n,i,j,k,t,m;
	memset(over,-1,sizeof(over));
	scanf("%d",&n);
//	fscanf(fin,"%d",&n);
	for(ans=0,i=1;i<=n;i++)
	{
		scanf("%d%d",&t,&k);
	//	fscanf(fin,"%d%d",&t,&k);
		long tmp = 0;
		if(k==0) over[i] = t;
		for(j=1;j<=k;j++)
		{
			scanf("%d",&m);
	//		fscanf(fin,"%d",&m);
			tmp = max(tmp,over[m]);
		}
		over[i] = tmp+t;
		ans = max(ans,over[i]);
	}
	printf("%ld\n",ans);
	return 0;
}

/*
 * poj1949 此代码AC不能
 * 树状DP的做法，小数据都能通过，但是提交就是RE。
 * 不确定是数组开小了还是哪有问题，一般都是数组小了。
 * */
#include<stdio.h>
#include<memory.h>
#include<algorithm>
using namespace std;

int time[10500],tree[55000],head[10500],over[10500];
long next[55000];
long n;
//FILE* fin;

void init()
{
	int i,j,k,m;
	long tot = 0;
	memset(next,0,sizeof(next));
	memset(head,0,sizeof(head));
	memset(over,-1,sizeof(over));
	scanf("%d",&n);
//	fscanf(fin,"%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&time[i],&k);
	//	fscanf(fin,"%d%d",&time[i],&k);
		if(!k) over[i] = time[i];
		for(j=1;j<=k;j++)
		{
		//	fscanf(fin,"%d",&m);
			scanf("%d",&m);
			tree[++tot] = m,next[tot] = head[i],head[i] = tot;
		}
	}
	return;
}
long dfs(int i)
{
	if(over[i]!=-1)
	  return over[i];

	long j,tmp = 0;
	for(j=head[i];j;j=next[j])
		tmp = max(tmp,dfs(tree[j]));

	over[i] = time[i]+tmp;
	return over[i];

}
int main()
{
	long ans,i;
//	fin = fopen("d.in","r");
	init();
	for(ans=0,i=n;i>=1;i--)
	  ans = max(ans,dfs(i));
	printf("%ld\n",ans);
//	fclose(fin);
	return 0;
}