hdu6007 Mr. Panda and Crystal dij+完全背包

我们只要求出每种宝石获得的最小花费,这道题就变成了完全背包。

我们回顾下方程 dp[v] = max(dp[v],dp[v – c[i]] + p[i]) v从1开始循环。

然后怎么求出每种宝石获得的最小花费呢?

我们回顾下题意,发现模型有些类似最短路,只不过每个点的dis是组成成分的dis的加权和。我们再回顾下,dij算法的原理,本质是一个贪心。我们易证,我们可以把dis转移改成每次读所有组成成分求dis,正确性依旧。我们只要在边上维护下,这条边属于哪个组成配方,然后到该配方里求出dis即可。

发表评论