题目内容

塔子哥是一名工薪族，每个月工资刚刚够支付日常开支，因此他总是需要在超市购买实惠的商品。

有一天，他进入了一家超市，发现超市正在举行一场特殊活动。当塔子哥花费原价买了一件商品时，他可以用半价买下一件右边相邻的商品(也可以用原价购买，这样该商品右边的商品就有次享受半价的机会)。但如果塔子哥半价购买了一件商品，那么下一件右边相邻的商品只能原价购买。

塔子哥有一定的存款，但是他想尽可能多地购买他喜欢的商品，因此他想知道在限制总价不超过 $x$ 的情况下，他最多可以获得多少喜爱度。

思路

动态规划，三维dp，$dp[i][j][0]$ 代表在考虑前 $i$ 个商品的基础上，总共花费了 $j$ 元时能得到的最大的喜爱度，$dp[i][j][1]$ 代表相同条件的基础上第 $i$ 个商品用原价购买时的最大喜爱度。

$dp[i][j][0] = max(dp[i-1][j-a[i]][0] + b[i], dp[i-1][j-a[i]][1] + b[i])$

$dp[i][j][1] = max(dp[i][j][0], dp[i-1][j-a[i]/2][0] + b[i], dp[i-1][j][1])$

在dp更新过程中得到最大值即可