本文共 2526 字，大约阅读时间需要 8 分钟。

Description

玩过Diablo的人对技能树一定是很熟悉的。一颗技能树的每个结点都是一项技能，要学会这项技能则需要耗费一定的技能点数。只有学会了某一项技能以后，才能继续学习它的后继技能。每项技能又有着不同的级别，级别越高效果越好，而技能的升级也是需要 耗费技能点数的。
　　有个玩家积攒了一定的技能点数，他想尽可能地利用这些技能点数来达到最好的效果。因此他给所有的级别都打上了分，他认为效果越好的分数也越高。现在他要你帮忙寻找一个分配技能点数的方案，使得分数总和最高。

Input

第一行是一个整数n（1<=n<=20）,表示所有不同技能的总数。接下来依次给出n个不同技能的详细情况。每个技能描述包括5行，第一行是该技能的名称，第2行是该技能在技能树中父技能的名称，为空则表示该技能不需要任何的先修技能便能学习。第3行是一个整数L（1<=L<=20），表示这项技能所能拥有的最高级别。第4行共有L个整数，其中第I个整数表示从地I-1级升到第I级所需要的技能点数（0级表示没有学习过）。第5行包括L个整数，其中第I个整数表示从第I-1级升级到第I级的效果评分，分数不超过20。在技能描述之后，共有两行，第1行是一个整数P，表示目前所拥有的技能点数。接下来1行是N个整数，依次表示角色当前习得的技能级别，0表示还未学习。这里不会出现非法情况。

Output

S，表示最佳分配方案所得的分数总和。

Sample Input

3
Freezing Arrow
Ice Arrow
3
3 3 3
15 4 6
Ice Arrow
Cold Arrow
2
4 3
10 17
Cold Arrow

3
3 3 2
15 5 2
10
0 0 1

Sample Output

42

思路

设f[i][j]为第i个点分配j点的最优解，则有：
$f_{x,j}=max(f_{x,j},f_{so{n}_{x,i},j,f_{so{n}_{x,i},j-q}+p})(x为节点，j为枚举的分配点数，q，p分别为花费和利润$
code:

#include<iostream>#include<cstdio>#include<algorithm>#include<string>#include<cstring>#include<cmath>#include<queue>#include<map>using namespace std;int n,p,son[1000][1000],f[1000][1000],u;struct fP{   	int l,xx;	int a[1000],b[1000];} b[1000];int data[100010];string x,ss[100190];int tot;int find_(string s){   	for (int i=1; i<=tot; i++)	{   		if (s==ss[i]) return i;	}	tot++; 	ss[tot]=s;	return tot;}void dfs(int x,int mx){   	int t[1010];	if (mx<0) return;	for (int i=1;i<=son[x][0];i++)	{   		for (int j=0;j<=mx;j++) t[j]=f[x][j];		if (b[son[x][i]].xx!=0)		{   			for (int j=0;j<=mx;j++) f[son[x][i]][j]=t[j];			dfs(son[x][i],mx);			for (int j=0;j<=mx;j++) f[x][j]=max(f[x][j],f[son[x][i]][j]);		}		int a1=0,b1=0; 		for (int k=b[son[x][i]].xx+1;k<=b[son[x][i]].l;k++)		{   			a1+=b[son[x][i]].a[k],b1+=b[son[x][i]].b[k];			if (mx-a1<0) break;			for (int j=0;j<=mx-a1;j++) f[son[x][i]][j]=t[j];			dfs(son[x][i],mx-a1);			for (int j=a1;j<=mx;j++) f[x][j]=max(f[x][j],f[son[x][i]][j-a1]+b1);		}	}	return;}int main(){   	cin>>n;	for (int i=1;i<=n;i++)	{   		getline(cin,x);		getline(cin,x);		data[i]=find_(x);		getline(cin,x);    	int y;		if (x!="") y=find_(x);    	else y=0;    	son[y][0]++;    	son[y][son[y][0]]=data[i];		cin>>b[data[i]].l;		for (int j=1;j<=b[data[i]].l;j++)		{   			cin>>b[data[i]].a[j];		}		for (int j=1;j<=b[data[i]].l;j++)		{   			cin>>b[data[i]].b[j];		}	}	cin>>p;	for (int i=1;i<=n;i++) cin>>b[data[i]].xx;	dfs(0,p);	cout<<f[0][p];    return 0;}