有 n 个位置排成一排，第 i 个位置都有一个分数 a_i（分数可能是正数，也可能是负数）。小爱从 1 号位置出发，最终要走到 n 号位置。当小爱在第 i 个位置时，有两种选择：
她可以直接走到下一个位置（也就是i+1 号位置）；
也可以选择跳到第 t_i 号位置（保证i<t_i）。
小爱的得分就是一路上经过的所有位置的分数之和，请问应该如何安排行动，才能使获得的分数之和达到最大？上海市计算机学会竞赛平台 | YACS
输入：3
4 -2 6
3 3
输出：10
这道题是比较简单的动态规划题。后面的结果不会对前面的产生影响（无后效性质）
所以，找到状态的转移方程，写下dp数组的定义，找到基础解就好了。
这里第1个位置4分，第三个位置6分，可以选择第1个位置到第2个位置，也能选择第1个位置跳到第3个位置(n=3， 执行完毕了)；
如何行动使得分数最大。假设dp[i]代表第i步的得分，那么dp[i+1]=dp[i]+a[i] 或者dp[t[i]]=dp[i]+a[t[i]]（这里之所以是dp[t[i]] 因为是跳到了t[i]步，dp代表的是i步的分数，所以哪里要改变）
知道这个思路以后，这道题就简单多了。注意dp[i]=-1e18是因为题目要求得分a[i]是有负数的，还挺小。
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
int a[maxn],t[maxn];
long long dp[maxn];
long long n;
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],dp[i]=-1e18;
for(int i=1;i<n;i++)cin>>t[i];
dp[1]=a[1];
for(int i=1;i<=n;i++){
dp[i+1]=max(dp[i+1],dp[i]+a[i+1]);
dp[t[i]]=max(dp[t[i]],dp[i]+a[t[i]]);
}
cout<<dp[n];
return 0;
}
