アルゴリズムコンテスト宝典動的計画魔法石鉱

【タイトル説明】魔法石鉱(Mine.cpp/c/pas)
家に帰る道を見つけるために、張琪曼は魔法をかけて、高維空間から「読者」という生物を召喚した.「読者」という生物は何でもできるという.彼らは時空の制限を通り抜けて、歴史の音、巨人の叫びを聞くことができる.しかし、今回の「読者」は、遠い昔から陰気な天頂星人が封印を破って再びこの空間に降りてきたことを厳しく警告している.彼女たちが早く準備しなければ、彼女たちのいるこの世界は修羅場になるだけでなく、「読者」のいる時空にも巻き込まれるだろう.最後に「読者」は彼女たちに宝の図を渡して、彼女たちが天頂星人の攻撃に対抗するために十分な魔法石のエネルギーを集めることができることを望んでいる.蔵宝図には、表に示すように、直線に並んだ魔法石鉱がいくつか表示されていることが知られています.
同時に、各鉱山には、図に示すように、この鉱山の魔法石を掘った後もどの鉱山を掘り続けることができるかを説明する説明書があります.
掘削ルールは、どの鉱山からでも開始し、どの鉱山が終了するまで、この鉱山の魔法石を掘り終わった後、掘り続けることができる鉱山の1つを選択して掘り続けることができますが、1つしか選択できません.1鉱を掘った後、2鉱を掘って、5鉱、6鉱を掘って、......しかし右に掘ることができて、振り返って左に掘ることができません.すみません、どのように掘れば一番多くの魔法石を掘ることができますか?
【入力形式】
第1の挙動は、n(n≦1000)個の鉱山があることを示す整数nであり、第2の挙動は、n個の鉱山の魔法石数を示す整数nであり、その後、n行は、各鉱山が掘削された後にどの鉱山を掘ることができるかを示す.
【出力形式】
最も多く掘られた魔法石の数.
【入力サンプル】
3
1 1 1
1 2 3
2 3
3
【出力サンプル】
3
//欲張りのような考えで、この解法は標答のものと同じかどうか分からない.これは私自身の解法だからだ.
//この考え方は、まず前処理をして、文字をすべて処理して、後の直接利用に便利にすることです
//主な考え:kノードの時、kノードに到達できるすべての重み値の最大のノードを探せばいい!

#include
#include
#include
#include
const int N=10000+10;
using namespace std;
int dp[N];
int a[N][N];
int mine[N];
bool isnumber(char c)
{
	if(c>='0' && c<='9')
		return true;
	return false;
}                                                           
int main()
{
	int n,x,num,k;
	char c;
	while(cin>>n)
	{
		memset(a,0,sizeof(a));
		for(int i=1; i<=n; i++)
			scanf("%d",&mine[i]);		
		for(int i=1; i<=n; i++)
		{
			scanf("%d",&x);
			k=0;
			do
			{
				num=0;
				while(isnumber(c=getchar()))
					num=num*10+c-'0';
				if(num>0)
						a[num][++a[num][0]]=x;
			}while(c!='
');
		}
		int ans=0;
		for(int i=1; i<=n; i++)
		{
			int Max=0;
			for(int j=1; j<=a[i][0]; j++)
			{
				Max=max(Max,mine[a[i][j]]);
			}
			mine[i]+=Max;
			ans=max(mine[i],ans);
		}
		printf("%d
",ans);
	} 
	return 0;
}