Description
你需要买\(n\)个商品，商品\(i\)需要的数目为\(needs_i\)，单价为\(price_i\)。同时有\(m\)个打包优惠，每个优惠\(special_i\)均为一个长度\(n+1\)的数组，其中前\(n\)个元素对应商品\(i\)的数目，最后一个元素对应打包优惠价格。求最低买入价格。
Constraints
- \(1 \le n \le 6\)
- \(0 \le price_i \le 10\)
- \(0 \le needs_i \le 10\)
- \(1 \le m \le 100\)
- \(0 \le special_{ij} \le 50\)
Solution
每4个bit可表示一个商品数目的状态（\(2^4 \gt 10\)），因此状压DP维护\(dp[S]\)即可。
\(dp[]\)内的分布可能是稀疏的，因此使用哈希表来维护。
Code
class Solution {
public:
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
int S = 0;
for(int i = 0, j = 0; i < needs.size(); j = ++i<<2) {
S |= needs[i] << j;
}
unordered_map<int, int> dp;
auto DP = [&](auto &&DP, int s) {
if(dp.count(s)) return dp[s];
int best = 0;
for(int i = 0, j = 0; i < price.size(); j = ++i<<2) {
int needi = s >> j & 0b1111;
best += price[i] * needi;
}
for(const auto &sp : special) {
int s2 = 0;
bool overflow = false;
for(int i = 0, j = 0; i < sp.size() - 1; j = ++i<<2) {
int needi = s >> j & 0b1111;
if(sp[i] > needi) {
overflow = true;
break;
}
s2 |= needi-sp[i] << j;
}
if(!overflow) {
best = min(best, sp.back() + DP(DP, s2));
}
}
return dp[s] = best;
};
return DP(DP, S);
}
};