技能树(difficult)【树形DP】

Time Limit:1000MS Memory Limit:65536K

Total Submit:18 Accepted:11

Description

　　玩过 D i a b l o Diablo Diablo的人对技能树一定是很熟悉的。一颗技能树的每个结点都是一项技能，要学会这项技能则需要耗费一定的技能点数。只有学会了某一项技能以后，才能继续学习它的后继技能。每项技能又有着不同的级别，级别越高效果越好，而技能的升级也是需要 耗费技能点数的。

　　有个玩家积攒了一定的技能点数，他想尽可能地利用这些技能点数来达到最好的效果。因此他给所有的级别都打上了分，他认为效果越好的分数也越高。现在他要你帮忙寻找一个分配技能点数的方案，使得分数总和最高。

Input

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

解题思路

它虽然是“技能树”，但是它输入可能是一个“技能森林”，

因此，我们需要一个编号为0的点，作为所有树的根节点。

int y;
		if(ss!="")
			yy=findd(ss);
		else yy=0;
		son[yy][++son[yy][0]]=num[i];
           

我们接下来分析如何DP

我们设 f [ i ] [ j ] f[i][j] f[i][j]表示当前节点用 j j j 点能量值可获得的最大值

我们分两种情况来做：

• 不升级技能的情况下能得到的最大分数。

  f [ d e p ] [ j ] = m a x ( f [ d e p ] [ j ] , f [ s o n [ d e p ] [ i ] ] [ j ] ) ; f[dep][j]=max(f[dep][j],f[son[dep][i]][j]); f[dep][j]=max(f[dep][j],f[son[dep][i]][j]);

• 升级技能的情况下能得到的最大分数。

  f [ d e p ] [ t ] = m a x ( f [ d e p ] [ t ] , f [ s o n [ d e p ] [ i ] ] [ t − p ] + q ) ; f[dep][t]=max(f[dep][t],f[son[dep][i]][t-p]+q); f[dep][t]=max(f[dep][t],f[son[dep][i]][t−p]+q);

代码

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
using namespace std;
int son[1010][1010],num[1010],l[1010],x[1010][1010],y[1010][1010],d[101000],f[1010][1010],n,m,tot;
string s[1010],ss;
int findd(string ss){
	for(int i=1;i<=tot;i++)
	{
		if(s[i]==ss)
			return i;
	}
	tot++;
	s[tot]=ss;
	return tot;
}
void dp(int dep,int k){
	int tmp[1010];
	if(k<0) return;
	for(int i=1;i<=son[dep][0];i++)
	{
		for(int j=0;j<=k;j++)
			tmp[j]=f[dep][j];
		if(d[son[dep][i]]!=0)
		{
			for(int j=0;j<=k;j++)
				f[son[dep][i]][j]=f[dep][j];//儿子继承父亲
			dp(son[dep][i],k);
			for(int j=0;j<=k;j++)
				f[dep][j]=max(f[dep][j],f[son[dep][i]][j]);//回溯更新答案
		}
		int p=0,q=0;
		for(int j=d[son[dep][i]]+1;j<=l[son[dep][i]];j++)
		{
			
			p+=x[son[dep][i]][j];
			q+=y[son[dep][i]][j];
			if(k<p)//儿子不能取了就直接停止继续取
				break;
			for(int t=0;t<=k-p;t++)
				f[son[dep][i]][t]=tmp[t];
			dp(son[dep][i],k-p);
			for(int t=p;t<=k;t++)
				f[dep][t]=max(f[dep][t],f[son[dep][i]][t-p]+q);
		}
			
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		getline(cin,ss);
		getline(cin,ss);
		num[i]=findd(ss);
		getline(cin,ss);
		int yy=0;
		if(ss!="")
			yy=findd(ss);
		else yy=0;
		son[yy][++son[yy][0]]=num[i];
		scanf("%d",&l[num[i]]);
		for(int j=1;j<=l[num[i]];j++)
			scanf("%d",&x[num[i]][j]);
		for(int j=1;j<=l[num[i]];j++)
			scanf("%d",&y[num[i]][j]);
	}
	scanf("%d",&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&d[num[i]]);
	dp(0,m);
	printf("%d",f[0][m]); 
}