1017: [JSOI2008]魔兽地图DotR
Time Limit: 30 Sec Memory Limit: 162 MBSubmit: 2597 Solved: 1010
[Submit][Status][Discuss]
Description
DotR (Defense of the Robots) Allstars是一个风靡全球的魔兽地图，他的规则简单与同样流行的地图DotA
(Defense of the Ancients) Allstars。DotR里面的英雄只有一个属性——力量。他们需要购买装备来提升自己的
力量值，每件装备都可以使佩戴它的英雄的力量值提高固定的点数，所以英雄的力量值等于它购买的所有装备的力
量值之和。装备分为基本装备和高级装备两种。基本装备可以直接从商店里面用金币购买，而高级装备需要用基本
装备或者较低级的高级装备来合成，合成不需要附加的金币。装备的合成路线可以用一棵树来表示。比如，Sange
and Yasha的合成需要Sange,Yasha和Sange and Yasha Recipe Scroll三样物品。其中Sange又要用Ogre Axe, Belt
of Giant Strength和 Sange Recipe Scroll合成。每件基本装备都有数量限制，这限制了你不能无限制地合成某
些性价比很高的装备。现在，英雄Spectre有M个金币，他想用这些钱购买装备使自己的力量值尽量高。你能帮帮他
吗？他会教你魔法Haunt（幽灵附体）作为回报的。
Input
第一行包含两个整数，N (1 <= n <= 51) 和 m (0 <= m <= 2,000)。分别表示装备的种类数和金币数。装备
用1到N的整数编号。接下来的N行，按照装备1到装备n的顺序，每行描述一种装备。每一行的第一个非负整数表示这
个装备贡献的力量值。接下来的非空字符表示这种装备是基本装备还是高级装备，A表示高级装备，B表示基本装备
。如果是基本装备，紧接着的两个正整数分别表示它的单价（单位为金币）和数量限制（不超过100）。如果是高
级装备，后面紧跟着一个正整数C，表示这个高级装备需要C种低级装备。后面的2C个数，依次描述某个低级装备的
种类和需要的个数。
Output
第一行包含一个整数S，表示最多可以提升多少点力量值。
Sample Input
5 A 3 6 1 9 2 10 1
1 B 5 3
1 B 4 3
1 B 2 3
8 A 3 2 1 3 1 7 1
1 B 5 3
5 B 3 3
15 A 3 1 1 5 1 4 1
1 B 3 5
1 B 4 3
Sample Output
33
对于这道题，我们设f[i][j][k]表示处理到第i个点，向父亲节点合并j个装备，花了k元钱的最大力量值（不包括合并的j个）。
设g[i][j]表示当前节点的前i个子树花了j元钱的最大力量（不包括合并的）。
我们先枚举购买当前装备的总数量b，
对于f的转移，我们枚举j，k，有转移方程f[i][j][k]=max{g[i][k]+p[i]*(b-j)}
对于g的转移，我们枚举子树tot，钱数j和当前子树的钱数k，有g[tot][j]=max{g[tot-1][j-k]+f[i][b*e[i].v][k]}
之后统计答案即可
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 using namespace std; 8 int read() { 9 ????int x=0,f=1;char ch=getchar();10 ????while(!isdigit(ch)){if(ch==‘-‘) f=-1;ch=getchar();}11 ????while(isdigit(ch)){x=x*10+ch-‘0‘;ch=getchar();}12 ????return x*f;13 }14 int n,m,cnt,tot,ans;15 int p[55],L[55],M[55];16 int f[55][105][2005];17 int g[55][2005],h[55][2005];18 char ch[5];19 int head[55],deg[55];20 struct data{int to,next,v;}e[20005];21 void add(int u,int v,int w){e[cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;cnt++;deg[v]++;}22 void dfs(int now) {23 ????if(head[now]<0) {24 ????????L[now]=min(L[now],m/M[now]);25 ????????for(int i=0;i<=L[now];i++)26 ????????????for(int j=i;j<=L[now];j++) f[now][i][j*M[now]]=(j-i)*p[now];27 ????????return ;28 ????}29 ????L[now]=214748364;30 ????for(int i=head[now];i>=0;i=e[i].next) {31 ????????int to=e[i].to;32 ????????dfs(to);33 ????????L[now]=min(L[now],L[to]/e[i].v);34 ????????M[now]+=e[i].v*M[to];35 ????}36 ????L[now]=min(L[now],m/M[now]);37 ????memset(g,-47,sizeof(g));38 ????g[0][0]=0;39 ????for(int b=L[now];b>=0;b--) {40 ????????int tot=0;41 ????????for(int i=head[now];i>=0;i=e[i].next) {42 ????????????tot++;43 ????????????for(int j=0;j<=m;j++)44 ????????????????for(int k=0;k<=j;k++){45 ????????????????????g[tot][j]=max(g[tot][j],g[tot-1][j-k]+f[e[i].to][b*e[i].v][k]);}46 ????????}47 ????????for(int i=0;i<=b;i++)48 ????????????for(int j=0;j<=m;j++)49 ????????????????f[now][i][j]=max(f[now][i][j],g[tot][j]+p[now]*(b-i));50 ????}51 }52 int main() {53 ????memset(head,-1,sizeof(head));54 ????memset(f,-47,sizeof(f));55 ????n=read(),m=read();56 ????for(int i=1;i<=n;i++) {57 ????????p[i]=read();58 ????????scanf("%s",ch);59 ????????if(ch[0]==‘A‘) {60 ????????????int x=read();61 ????????????while(x--) {62 ????????????????int v=read(),num=read();63 ????????????????add(i,v,num);64 ????????????}65 ????????}66 ????????else M[i]=read(),L[i]=read();67 ????}68 ????int sum=0;69 ????for(int x=1;x<=n;x++) {70 ????????if(!deg[x]) {71 ????????????dfs(x);72 ????????????sum++;73 ????????????for(int i=0;i<=m;i++)74 ????????????????for(int j=0;j<=i;j++)75 ????????????????????for(int k=0;k<=L[x];k++)76 ????????????????????????h[sum][i]=max(h[sum][i],h[sum-1][j]+f[x][k][i-j]);77 ????????}78 ????}79 ????int ans=0;80 ????for(int i=0;i<=m;i++) ans=max(ans,h[sum][i]);81 ????cout<<ans;82 }[BZOJ1017][JSOI2008]魔兽地图DotR 树形dp
原文地址：http://www.cnblogs.com/wls001/p/7647387.html