题目：http://www.tyvj.cn/Problem_Show.asp?id=1258

题意：中文题，题意就不讲了。

分析；一道经典的DP题。如果你是C或C++选手，你只能用字符串读入数据，为什么呢？因为每一行并没有告诉你有几个数字，只是让你通过换行符来判断每一层的状态。此题输入特别坑人，假如你TLE在第1和第3个点，那是因为数据的末尾有可能会有换行或空格，所以要读到EOF才能结束。

dp的思路应该是很明显，方程也很好写，对于第i层，它有可能是由输入的数据来决定前驱状态，所以方程就为：dp[i]=max(dp[i],dp[j]+tree[i]);  j为枚举i的所有前驱层，tree为每一层礼物的价值。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
int tree[105],dp[105];
vector <int> Pre[105];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
       scanf("%d",&tree[i]);
       if(getchar()=='\n') continue;
       char ch;
       vector <char> T;
        while(ch!=EOF){
          ch=getchar();
          if(ch>='0'&&ch<='9')
           T.push_back(ch);
          else{
            int pre=0,ss=1;
            for(int j=T.size()-1;j>=0;j--){
             pre+=(T[j]-'0')*ss;
             ss*=10;
            }
            Pre[pre].push_back(i);
            T.clear();
          }
          if(ch=='\n') break;
        }
        dp[i]=tree[i];
    }
    for(int i=2;i<=n;i++)
     for(int j=0;j<Pre[i].size();j++)
      dp[i]=max(dp[i],dp[Pre[i][j]]+tree[i]); 
    int ans=-99999999;
    for(int i=1;i<=n;i++)
    ans=max(ans,dp[i]);
    cout<<ans<<endl;
    //system("pause");
    return 0;
}