#洛谷 P1860 新魔法药水

神奇的DP

大概是用DP预处理要预处理的内容

然后用DP预处理

最后DP背包跑答案

 

卡了我很久有必要详细讲一下

题目描述

商店里有N种药水,每种药水都有一个售价和回收价。小S攒了V元钱,还会M种魔法,可以把一些药水合成另一种药水。他一天可以使用K次魔法,问他一天最多赚多少钱?

输入输出格式

输入格式:

第一行四个数N、M、V、K

接下来N行,每行两个数,表示药水的售价和回收价。

接下来M行,每行若干个数,第一个数表示魔法的成品,第二个数是原料的种数,接下来为各种原料的编号

输出格式:

一个数,表示小S的最大利润

·

N<=60 M<=240

V<=1000

k<=30

我们先考虑这是个背包

然后很自然的只需要求每个物品的min 购买价,然后二位费用xjb转移就可以得出答案

DP求这个部分.

因为有魔法,所以设计状态dx[i][j]表示物品i在当前用了j次魔法的情况下最小的购买价,这样才能当做背包来DP

dx怎么求呢?也不好求,所以这就是卡我的地方,我一开始还以为是DFS求

 

厚颜无耻的看题解……

你需要在枚举每个魔法w的时候都dp处理出 第w个魔法所需的前x个物品 用y次魔法 可以得到的最小购买价

设计状态ori[x][y]表示这样,每次枚举了一个魔法w都要求一次ori,注意y≤枚举的魔法次数

然后DP一波ori,这个很简单,写过几道提高水平的DP就会求

然后用ori[w需要的物品总数][枚举魔法次数-1]更新dx[w产成品][枚举的魔法次数]

·

这样我们就有了dx

xjb背包即可.XXXD

USACO 3.4 “破锣摇滚”乐队 Raucous Rockers

题目描述

你刚刚继承了流行的“破锣摇滚”乐队录制的尚未发表的N(1 <= N <= 20)首歌的版权。你打算从中精选一些歌曲,发行M(1 <= M <= 20)张CD。每一张CD最多可以容纳T(1 <= T <= 20)分钟的音乐,一首歌不能分装在两张CD中。CD数量可以用完,也可以不用完

不巧你是一位古典音乐迷,不懂如何判定这些歌的艺术价值。于是你决定根据以下标准进行选择:

1.歌曲必须按照创作的时间顺序在所有的CD盘上出现。(注:第i张盘的最后一首的创作时间要早于第i+1张盘的第一首)

2.选中的歌曲数目尽可能地多

一开始我看见这道题打了一道背包……

结果很惨的GG了……

我们设f[n][m][k]表示前n首歌按顺序尽量向m张盘里装,然后附加k分钟所能装的最多歌曲数

那么,显然k<=T,因为……如果k>T那f[i][j][k]等价于f[i][j+1][k-T],所以k>T是没有意义的

我们来考虑第n首歌装到第m+1张盘里的决策,也就是转移f[n][m][k] (因为m张盘外加k分钟,如果用那k分钟,也就是向m+1张里面装)

先初始化一下,也就是尝试放弃第i首歌

如果第j+1张盘的前k分钟能装的下,

那就不装,或者用前j张和j+1张的前k-a[i]分钟装前i-1首,第j+1张的最后a[i]分钟(歌曲的长度)装第i首

这两个里面取max

如果第j+1张盘的前k分钟装不下,

那么,假如说存在第j张盘(可以有j=0而k>0,也就是装第一张),那么就不装,或者用前j-1张盘外加第j张盘的T-a[i]分钟装前i-1首,用第j张盘装第i首试一下 (那么,就相当于尽量把第i首歌往j整张盘里装,如果a[i]小于T,那一定能装上,而如果T<a[i]了,那这首歌显然只能放弃)。

我们为什么要有第二个方程?原因在于k不一定大于a[i],而如果这首歌对决策有影响,那么T一定大于a[i],所以有必要试着装一下。

那么整个方程……

然后这是代码……