1 条题解
-
0
何老师 (root) LV 0 MOD @ 2023-02-21 23:05:34
有条件背包/有依赖背包/捆绑背包,同NOIP2006提高组的【金明的预算 】
二次动归:
设f(i,j) 表示前 i 种游戏机,花费 j 元钱,能得到的最大收益
对于第i种游戏机,其选择有:
1、不买,此时运行于它上面的游戏也不能买,则 f(i,j)=f(i-1,j)2、买,此时需要先花去C[i]元买游戏机,然后再考虑运行于其上的游戏,是一个0/1背包问题:
设d(j) 表示花j元钱去买游戏机i上的游戏,能得到的最大收益
d(j)= max(d[j],d[j-p[i][k]] + e[i][k])于是对于f(i,j):假设花x元用于第i种游戏机及其游戏,的最大收益是d[x-C[i]],则剩下 j-x 用于前面 i-1 款游戏的最大收益f(i-1,j-x),于是有:
f(i,j) = max{f(i-1,j-x) + d[j-x-C[i]] | C[i]<=x<=j}
这种算法时间复杂度:O(n*m*m),会超时!优化:
对算法1中选择购买第i种游戏,对于f(i,j)中j元分两部分,j-x用于前面i-1种游戏机,x用于第i中游戏机,于是我们
设:d[j]表示前i种游戏机花j元钱,在第i种游戏机必买的情况下,的最大收益
d(j)的初值: d(j)=f(i-1,j-C[i])
然后: d(j)= max{ d(j),d(j-p[i][k]+e[i][k])
于是f(i,j)= max(f(i-1,j) , d(j) )
此时的时间复杂度为:O(n*10*m)
- 1