- 传送门 -
http://www.lydsy.com/JudgeOnline/problem.php?id=1017
1017: [JSOI2008]魔兽地图DotR
Time Limit: 30 Sec Memory Limit: 162 MB
Submit: 2450 Solved: 971
[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
10 59
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 为根节点的整个子树花费 k 元，向父节点贡献 j 个装备 i 的最大价值.
mum[i] : 表示装备 i 的最大拥有量(考虑到我们所拥有的钱是一定的,所以它不一定是最大购买量).
cost[i] : 基本装备 i 的价格.
need[i] : 合成一个对应高级装备时所需 i 的数量.
pr[i] ：装备 i 的力量值.
money : 所拥有的钱的数量.
让我们从树的底部开始往上处理.
对于叶子节点 i 有 :
mum[i] = min(mum[i],money/cost[i])
f[i][j][rcost[i]] = (r-j)pr[i]
对于非叶子节点 i 有 :
mum[i] = min(m[i],mum[v]/need[v])
f[i][j][k] = max(f[i][j][k], g[i][j][k-l]+f[v][j*need[v]][l]) ( v 表示 i 的子节点,0 < j < m[i] )
( 先假设这 j 个点都被贡献给 i 父节点了,所以不考虑 i 装备的力量值 )
这里出现了一个数组 g ,它表示的是处理完 v 的前一个子节点后, f 数组的情况.
因为对于一个贡献值 j 来说,我们需要 i 每一个儿子都贡献 need[v]*j 个, 所以递推过程中(金钱为 k )需要考虑满足
当前儿子( v )可以贡献 jneed[v] 个 :
f[v][jneed[v]][l] > 0 (l < k)
v 之前每一个儿子都能贡献 j * need[v'] 个(v' 表示 v 之前的儿子) :
f[i][j][k-l] > 0
(用金钱 l 来购买 jneed[v], 金钱 k-l 来购买 v 之前的儿子 , 假设此时的 f[i][j][k-l]还未被儿子 v 更新, 则它可以表示用金钱 k-l 来购买 jneed[v'] 用以合成, 剩下的钱(不一定存在)购置的装备不合成 所取得的最大价值).
因为 f[i][j][k] 是时刻更新的,所以我们可以另取一数组 g 来记录每用一子节点更新后, f 数组的情况.
更新完节点 i 我们考虑 : 我们得到的f[i][j][k],都是建立在这 j 个点都被贡献给 i 的父节点的基础上的 , 那如果(部分)节点 i 被保留而没有贡献呢???
f[i][j][k] = max(f[i][j][k] , max{ f[i][m][k] + pr[i]*(m-j) } ) (j < m < mum[i])
(在原本要贡献 m 个的情况下, 我们偷偷地保留下(m-j)个,于是实际贡献量变成了 j ,获得这(m-j)个的力量并以此更新 f[i][j][k])
细节见代码.
PS :
题意中有一个bug.
如果没有高级装备呢???
这道题在一个神秘时间被增加了一组没有高级装备的数据直接导致众多古老题解的WA...
树都没了就剩几个点还有什么合成路线???
特判一下然后一个暴力多重背包敲过去...
就是这样...
- 代码 -
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define FOR(i,a,b) for(int i = a; i <= b; i++)
using namespace std;
const int maxn = 55;
const int M = 2005;
const int inf = 0x7fffffff;
int f[maxn][105][M],g[M],pr[maxn];
int cost[maxn],mum[maxn],fa[maxn],need[maxn];
int n,m,ans = 0;
bool flag = false;
vector<int> poi[maxn];
void read(int &x) {
char ch = getchar(); x = 0;
while(ch > '9' || ch < '0') ch = getchar();
while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
}
void init() {
read(n); read(m);
char ch,_ch; int q,a,b;
FOR(i,1,n) {
scanf("%d%c%c",&pr[i],&_ch,&ch);
if(ch == 'A') {
read(q);
FOR(j,1,q) {
read(a), read(b);
poi[i].push_back(a);
fa[a] = i; need[a] = b;
}
flag = true;
}
else read(cost[i]), read(mum[i]);
}
}
void dfs(int p) {
if(poi[p].size() == 0) {
mum[p] = min(mum[p],m/cost[p]);
FOR(i,0,mum[p]) FOR(j,0,i)
f[p][j][i*cost[p]] = (i-j)*pr[p];
return;
}/* 叶子节点的处理 */
mum[p] = inf;
for(int i = 0,v; i < poi[p].size(); i++) {
v = poi[p][i];
dfs(v);
mum[p] = min(mum[p],mum[v]/need[v]);
}/* 非叶子节点最大拥有量的处理 */
FOR(i,0,mum[p]) f[p][i][0] = 0;/* 预处理 */
for(int i = 0,v; i < poi[p].size(); i++) { /* 考虑每一个儿子 */
v = poi[p][i];
FOR(j,0,mum[p]) {
memcpy(g,f[p][j],sizeof f[p][j]); /* v 之前的儿子的情况 */
memset(f[p][j],-1,sizeof f[p][j]); /* 可能因为 v 导致原本成立的某种情况不再成立,所以先把数组 f 全部赋为 -1 */
FOR(k,0,m) FOR(l,0,k) {
if(g[k-l] != -1 && f[v][j*need[v]][l] != -1)
/* v 之前的儿子花费 k-l 成立 */ /* v 花费 l 成立 */
f[p][j][k] = max(f[p][j][k], g[k-l]+f[v][j*need[v]][l]);
}
}
}
FOR(k,0,mum[p]) FOR(l,k,mum[p]) FOR(i,0,m) {
if(f[p][l][i] != -1)
f[p][k][i] = max(f[p][k][i],f[p][l][i] + (l-k)*pr[p]), /* 考虑本要向 i 的父节点贡献的 l 个节点中有 (l-k) 个被保留了,实际贡献量为 k (可更新) */
ans = max(ans,f[p][k][i]);
}
}
void work() { /* 强行的多重背包 */
int q[55],qe[55];
FOR(i,1,n)
for(int j = 0,s,t; j < cost[i]; j++) {
s = 0 ,t = 0;
for(int k = 0; k*cost[i] + j <= m; k++) {
int val = g[k*cost[i] + j] - k * pr[i];
if(s < t && val >= q[t-1]) t--;
q[t] = val;
qe[t++] = k;
g[k*cost[i] + j] = q[s] + k * pr[i];
if(s + mum[i] == k) s++;
}
}
printf("%d
",g[m]);
}
int main() {
init();
if(!flag) { work(); return 0; }
memset(f,-1,sizeof f);
FOR(i,1,n) {
if(fa[i] == 0) {
dfs(i);
break;
}
}
printf("%d
",ans);
return 0;
}