本文主要是介绍试题 算法训练 强力党逗志芃，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
逗志芃励志要成为强力党，所以他将身上所以的技能点都洗掉了重新学技能。现在我们可以了解到，每个技能都有一个前提技能，只有学完了前提技能才能学习当前的技能（有一个最根本的技能不需要前提技能）。学习每个技能要消耗一个技能点，然后可以获得这个技能的威力值。由于逗志芃要陪妹子，所以他希望你教他如何点技能使得威力值最大从而成为强力党。
输入格式
第一行两个数n，m表示有n个技能和m个技能点。第二行有n个数，第i个数表示第i个技能的威力值。
之后的n-1行，每行两个数x,y，表示y技能的前提技能是x，也就是说先学第x个技能才能学弟y个技能。输出格式
一个数，最大的威力值。
样例输入
3 2
1 10 20
1 2
1 3样例输出
21
数据规模和约定
0<n,m<=200, 技能的威力值不超过200。
思路：树形DP
代码如下：
#include<bits/stdc++.h>
using namespace std;
vector<int>tree[210];
int a[210];
int isRoot[210];
int f[210][210][210];//i为根结点，j为遍历到第j个结点了，k为能选多少个结点
int n,m;
void dfs(int x){for(int i=0;i<tree[x].size();i++)dfs(tree[x][i]);//先更新子结点 f[x][1][1]=a[x];//只选了根结点f[x][1][0]=0;//一个都没选for(int i=2;i<=tree[x].size()+1;i++){//从2开始是因为根结点x的两种情况已经遍历完了；tree[x].size只是子元素的个数，还得+1，表示包括x int v=tree[x][i-2];//i-2也很好理解,对于一个数，根结点是1，则第一个子结点是2，它的编号也就是tree[x][i-2] for(int j=0;j<=m;j++){for(int k=0;k<j;k++){f[x][i][j]=max(f[x][i][j],f[x][i-1][j-k]+f[v][tree[v].size()+1][k]);//tree[v].size()+1是子结点数加根结点数 }}} }
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}memset(isRoot,true,sizeof(isRoot));for(int i=1;i<=n-1;i++){int key,value;cin>>key>>value;isRoot[value]=false;tree[key].push_back(value);}for(int i=1;i<=n;i++){if(isRoot[i]){dfs(i);cout<<f[i][tree[i].size()+1][m]<<endl;}}return 0;
}这篇关于试题 算法训练 强力党逗志芃的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
