题目链接

bzoj1017: [JSOI2008]魔兽地图DotR

题解

设dp[i][j][k]表示以i为根的子树中，有j个i节点用于和成上层，花费为k的最大收益
枚举合成l个i节点，然后用剩余的钱在子树中制造一些别的power
g[i][j]表示对于当前子树的前i棵子树花费j能得到的最大收益
得到g[i][j] = g[i - 1][k] + dp[v][need[v] * l][j - k] //注意，这里的已经转移保证了能合成上层l个
dp[x][j][k] = max(g[totson][k]))
最后背包合并
注意合法装态转移

代码

/*设dp[i][j][k]表示以i为根的子树中，有j个i节点用于和成上层，花费为k的最大收益枚举合成l个i节点，然后用剩余的钱在子树中制造一些别的powerg[i][j]表示对于当前子树的前i棵子树花费j能得到的最大收益得到g[i][j] = g[i - 1][k] + dp[v][need[v] * l][j - k] //注意，这里的已经转移保证了能合成上层l个 dp[x][j][k] = max(g[totson][k])) 最后背包合并注意合法装态转移 */ #include<bits/stdc++.h> using namespace std; ?inline int read() { ????int x = 0,f = 1; ????char c = getchar(); ????while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();} ?????while(c <= '9' && c >= '0')x = x * 10 + c - '0',c = getchar(); ????return x * f; } #define INF 1000000007 int n,m; const int maxn = 87; const int maxm = 2007; int limit[maxn],cost[maxn],power[maxn]; struct node { ????int v,next,w; }edge[20007]; int deg[maxn]; ?int dp[maxn][maxn * 2][maxm]; int g[maxn][maxm]; int num,head[maxn << 1]; void add_edge(int u,int v,int w) { ????edge[++ num].v = v;edge[num].w = w; edge[num].next = head[u]; head[u] = num; } void dfs(int x) { ????if(!head[x]) { ?????????for(int i = 0;i <= limit[x];++ i) for(int j = 0;j <= i;++ j) dp[x][j][i * cost[x]] = (i - j) * power[x]; ??????????return ; ????} ????limit[x] = INF; ????for(int i = head[x];i;i = edge[i].next) { ????????int v = edge[i].v; ????????dfs(v); ????????limit[x] = std::min(limit[x],limit[v] / edge[i].w); ????????cost[x] += cost[v] * edge[i].w; ????} ????limit[x] = std::min(limit[x],m / cost[x]); ????memset(g,-0x3f3f3f3f,sizeof g); g[0][0] = 0; // ?printf("%d\n",g[1][1]); ????int tmp = 0,tot = 0; ????for(int l = limit[x];l >= 0;-- l) { ????????tot = 0,tmp = 0; ????????for(int v,i = head[x];i;i = edge[i].next) { ????????????tot ++; ????????????????v = edge[i].v; //tmp += cost[v] * edge[i].w; ????????????for(int j = 0/*tmp*/;j <= m;++ j) ????????????????for(int k = 0/*tmp*/;k <= j;++ k) ????????????????g[tot][j] = std::max(g[tot][j],g[tot - 1][k] + dp[v][edge[i].w * l][j - k]); ????????} ????????for(int i = 0;i <= l;++ i) for(int k = 0;k <= m;++ k) ????????????dp[x][i][k] = std::max(dp[x][i][k],g[tot][k] + power[x] * (l - i)); ??????} } int h[maxn][maxm]; int main() { memset(dp,-0x3f3f3f3f,sizeof dp); ???n = read(),m = read(); ?????char op[10]; ????for(int a,b,c,d,i = 1;i <= n;++ i) { ????????power[i] = read(); ????????scanf("%s",op); ????????if(op[0] == 'A') { ????????????b = read(); ????????????for(int j = 1;j <= b;++ j) { ????????????????c = read(),d = read(); ????????????????add_edge(i,c,d); deg[c] ++; ????????????} ????????} else ?{ ????????????cost[i] = read(),limit[i] = read(); ????????????if(cost[i]) limit[i] = std::min(limit[i],m / cost[i]); ????????} ????} ????int tot = 0; ????for(int x = 1;x <= n;++ x) { ????????if(!deg[x]) { ????????????dfs(x); ????????????tot ++; ????????????for(int i = 0;i <= m;++ i) ????????????????for(int j = 0;j <= i;++ j) { ????????????????????for(int k = 0;k <= limit[x];++ k) { ????????????????????????h[tot][i] = max(h[tot][i],h[tot - 1][j] + dp[x][k][i - j]); ?????????????????????????????} ?????????????????} ?????????} ?????} ?????int ans = 0; ?????for(int i = 0;i <= m;++ i) ????????ans = std::max(ans,h[tot][i]); ??????printf("%d\n",ans); 

bzoj1017: [JSOI2008]魔兽地图DotR

原文地址：https://www.cnblogs.com/sssy/p/9279136.html