【BZOJ1016】最小生成树计数

【BZOJ1036】树的统计

【BZOJ1017】魔兽地图

Zarxdy34 posted @ 2015年11月02日 20:56 in BZOJ with tags 树形DP , 561 阅读

树形DP，f[i][j][k]表示第i个装备，留j个用于更高级的装备的合成，花费k的钱获得最大的力量值。

枚举合成装备x共l件，g[i][j]表示合成l件x装备的情况下，x的前i个子树（所需低级装备）用j的钱还能最多获得多大的力量值。

BZOJ1017
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105	`#include <cmath>` `#include <cstdio>` `#include <cstring>` `#include <algorithm>` `typedef` `long` `long` `LL;` `using` `namespace` `std;` `const` `int` `maxn=55,maxm=2010,maxlim=110,inf=~0U>>1,ninf=-(inf>>2);` `inline` `char` `readchar() {char` `ch;while` `((ch=getchar())==' '` `\|\| ch=='\n');return` `ch;}` `inline` `void` `read(int` `&x) {char` `ch;while` `((ch=getchar())<'0'` `\|\| ch>'9');x=ch-'0';while` `((ch=getchar())<='9'` `&& ch>='0') x=x10+ch-'0';}` `struct` `Equipment` `{` `int` `c[maxn],t[maxn],cs;` `int` `str,cost,lim;` `int` `type;` `}E[maxn];` `int` `f[maxn][maxlim][maxm],g[maxn][maxm];` `int` `degree[maxn];` `int` `root;` `int` `n,m;` `void` `Calc_G(int` `x,int` `l)` `{` `for` `(int` `i=0;i<=n;i++)` `for` `(int` `j=0;j<=m;j++) g[i][j]=ninf;` `g[0][0]=0;` `for` `(int` `i=1;i<=E[x].cs;i++)` `for` `(int` `j=0;j<=m;j++)` `for` `(int` `k=lE[x].t[i]E[E[x].c[i]].cost;k<=j;k++)` `g[i][j]=max(g[i][j],g[i-1][j-k]+f[E[x].c[i]][lE[x].t[i]][k]);` `}` `void` `Calc_F(int` `x,int` `l)` `{` `for` `(int` `i=0;i<=l;i++)` `for` `(int` `j=lE[x].cost;j<=m;j++)` `f[x][i][j]=max(f[x][i][j],g[E[x].cs][j]+(l-i)E[x].str);` `}` `void` `DP(int` `x)` `{` `if` `(E[x].type==0)` `{` `for` `(int` `i=0;i<=E[x].lim;i++)` `for` `(int` `j=iE[x].cost;j<=m;j++)` `f[x][i][j]=min(j/E[x].cost-i,E[x].lim-i)E[x].str;` `return;` `}` `for` `(int` `i=1;i<=E[x].cs;i++) DP(E[x].c[i]);` `E[x].lim=inf;` `for` `(int` `i=1;i<=E[x].cs;i++)` `{` `E[x].lim=min(E[x].lim,E[E[x].c[i]].lim/E[x].t[i]);` `E[x].cost+=E[x].t[i]*E[E[x].c[i]].cost;` `}` `E[x].lim=min(E[x].lim,m/E[x].cost);` `for` `(int` `l=0;l<=E[x].lim;l++)` `{` `Calc_G(x,l);` `Calc_F(x,l);` `}` `}` `void` `Init()` `{` `read(n),read(m);` `for` `(int` `i=0;i<=n;i++)` `for` `(int` `j=0;j<=maxlim;j++)` `for` `(int` `k=0;k<=maxm;k++)` `f[i][j][k]=ninf;` `for` `(int` `i=1;i<=n;i++)` `{` `read(E[i].str);` `if` `(readchar()=='B')` `{` `E[i].type=0;` `read(E[i].cost),read(E[i].lim);` `E[i].lim=min(E[i].lim,m/E[i].cost);` `}` `else` `{` `read(E[i].cs);` `for` `(int` `j=1;j<=E[i].cs;j++) read(E[i].c[j]),read(E[i].t[j]),degree[E[i].c[j]]++;` `E[i].type=1;` `}` `}` `for` `(int` `i=1;i<=n;i++)` `if` `(!degree[i]) root=i;` `}` `void` `Print()` `{` `int` `ans=0;` `for` `(int` `i=1;i<=n;i++) ans=max(ans,f[i][0][m]);` `printf("%d\n",ans);` `}` `int` `main()` `{` `Init();` `DP(root);` `Print();` `return` `0;` `}`

评论 (0)