Gravatar
assassain
积分:1068
提交:233 / 619

Gravatar
啊吧啦吧啦吧
积分:544
提交:169 / 323

Gravatar
葳棠殇
积分:1418
提交:362 / 782
╮(╯▽╰)╭,这题调跪了DP

Gravatar
落尘
积分:846
提交:285 / 527
结构体的构造函数。。。坑。。。

题目 1189 有线电视网
2015-06-13 11:24:10
Gravatar
OIdiot
积分:596
提交:210 / 388
f[i][j]表示i为根节点,有j个子节点时的最大盈利注意会取到负数!
Profit[i]表示i节点的利润。
ChildNum[i]表示以i为根节点的叶子节点的个数。
child[i]保存i的子节点。
Dp:
枚举子节点:f[x][i]=Max(f[x][i],f[tmpNum][j]+f[x][i-j]-tmpCost);
如果x到了叶子节点:f[x][1]=Profit[x]; ChildNum[x]=1;