解题思路
这是带“相邻半价”约束的背包。物料从左到右排列，半价资格只能由“刚按原价买下的上一件”传给当前件。
令 dp[i][j][0] 表示考虑前 i 件、花费恰好为 j，且第 i 件按原价购买时的最大收益；dp[i][j][1] 表示同样花费下，第 i 件不是“原价购买”（半价购买或未购买）时的最大收益。收益为 0 的状态视为不可达（题目保证 bi≥1）。
转移：
- 第 i 件原价购买：从 dp[i−1][j−ai][∗] 加上 bi 得到 dp[i][j][0]；
题目内容
装配线旁从左到右摆了 n 种物料，第 i 种标价为偶数 ai，带来的装配收益为 bi。采购员必须按从左到右的顺序决定买或不买，总花费不能超过预算 x。
若某件按原价买入，则其右侧相邻下一件可以选择半价；若某件按半价买入，则右侧下一件不能再半价，只能原价买或放弃。未购买的物料不会把半价资格传给更右侧。第一件不能半价。
请计算花费不超过 x 时能获得的最大收益之和。若一件都买不起，答案为 0。
约束：1≤n,x,ai≤103，1≤bi≤1000000000，且所有 ai 均为偶数。
输入描述
