淮南市城乡建设档案馆网站,初创公司 建网站,南宁定制网站建设,网站建设报价模板下载Description 网上出现了一种高科技产品——人品测试器。只要你把你的真实姓名输入进去#xff0c;系统将自动输出你的人品指数。yzx不相信自己的人品为0。经过了许多研究后#xff0c;yzx得出了一个更为科学的人品计算方法。这种方法的理论依据是一个非常重要的结论#xff…Description 网上出现了一种高科技产品——人品测试器。只要你把你的真实姓名输入进去系统将自动输出你的人品指数。yzx不相信自己的人品为0。经过了许多研究后yzx得出了一个更为科学的人品计算方法。这种方法的理论依据是一个非常重要的结论人品具有遗传性。因此一个人的人品完全由他的祖先决定。yzx提出的人品计算方法相当简单只需要将测试对象的k个祖先的人品指数可能为负数加起来即可。选择哪k个祖先可以由测试者自己决定但必须要满足这个要求如果除自己的父母之外的某个祖先被选了那么他的下一代必需要选不允许跳过某一代选择更远的祖先否则将失去遗传的意义。非常不幸的是yzx测试了若干次他的人品值仍然不能为一个正数。现在yzx需要你帮助他找到选择祖先的最优方案使得他的人品值最大。 Input 第一行是两个用空格隔开的正整数n和k其中n代表yzx已知的家谱中共有多少人包括yzx本身在内k的意义参见问题描述。第二行有n-1个用空格隔开的整数可能为负这些数的绝对值在2^15以内。其中第i个数表示编号为i1的人的人品值。我们规定编号为1的人是yzx。接下来n行每行有两个用空格隔开的数其中第i行的两个数分别表示第i个人的父亲和母亲的编号。如果某个人的父亲或母亲不在这个家谱内则在表示他的父亲或母亲的编号时用0代替。除yzx以外的所有人都是yzx的祖先他们都会作为父亲或母亲被描述到。每个人都不可能同时作为多个人的父亲或者是母亲。 Output 一个整数表示yzx能够得到的最大人品值。 Sample Input 6 3-2 3 -2 3 -12 34 50 60 00 00 0 Sample Output 4样例说明下图显示了输入样例所描述的家谱图。括号里的数表示的是该人的人品值。 4(-2) 5(3) 6(-1) \ / / \ / / 2(-2) 3(3) \ / \ / 1 ---yzx 显然选择祖先2、3、5能使yzx的人品值达到最大。这个最大值为4表示yzx能够得到的最大人品值。 Data Constraint 50%的数据n10。100%的数据n100。 题解 这题显然就是一个树形dp设f[i][j]为在i为根的子树里选了j个祖先的最大人品值那么就可以枚举左子树里选祖先的个数i然后右子树里就是sum-i-1因为还要包括自己然后取个max就好了代码 1 #include cstdio2 #include iostream3 #define N 2104 #define inf 0x7ffffff5 using namespace std;6 struct edge { int x,y,v; }e[N];7 int n,k,p[N][N],f[N][N];8 int dp(int x,int sum)9 {
10 if (p[x][sum]) return f[x][sum];
11 if (!sum) return f[x][sum]0;
12 if (!x) return f[x][sum]-inf;
13 if (sum1) return f[x][sum]e[x].v;
14 int ans-inf;
15 for (int i0;isum;i) ansmax(ans,e[x].vdp(e[x].x,i)dp(e[x].y,sum-i-1));
16 p[x][sum]1,f[x][sum]ans; return ans;
17 }
18 int main()
19 {
20 scanf(%d%d,n,k);
21 for (int i2;in;i) scanf(%d,e[i].v);
22 for (int i1;in;i) scanf(%d%d,e[i].x,e[i].y);
23 printf(%d,dp(1,k1));
24 } 转载于:https://www.cnblogs.com/Comfortable/p/10316847.html
