LeetCode 638. Shopping Offers
原题链接
中等
作者:
孤独时代的罗永浩
,
2020-08-11 06:57:04
,
所有人可见
,
阅读 568
思路:
因为每一种商品最多买六个,这里用一个七进制的数字来表示,每次枚举可以使用的券对当前的状态进行改变后递归,最后和不用券的方式进行比较得到答案
class Solution {
public:
int F[120000];
vector<int> p;
vector<pair<vector<int>, int>> spec;
vector<int> ne;
//将vector转换成为一个七进制的数字
int vec2int(vector<int> &x)
{
int ret = 0;
for(int i = 0, j = 1; i < 6; i++, j *= 7)
ret += j * x[i];
return ret;
}
//确定curr的每一位是否都大于items,保证没有多选商品
int check(int curr, int items)
{
for(int i = 0; i < 6; i++)
{
if(curr % 7 < items % 7)
return 1;
curr /= 7;
items /= 7;
}
return 0;
}
int dfs(int status)
{
if(status == 0)
return 0;
if(F[status] != -1)
return F[status];
//初始化成无穷大
int ret = 1 << 30;
for(int i = 0; i < spec.size(); i++)
{
int curr = status;
int total = 0;
//将每一个special里面包含的东西转换成为7进制数字
int item = vec2int(spec[i].first);
if(item == 0) continue;
while(true)
{
//如果使用当前的购物券会导致多买东西,那么退出
if(check(curr, item))
{
break;
}
else
{
total += spec[i].second;
curr -= item;
ret = min(ret, dfs(curr) + total);
}
}
}
int temp = 0;
int curr = status;
for(int i = 0; i < 6; i++)
{
int v = curr % 7;
temp += v * p[i];
curr /= 7;
}
ret = min(ret, temp);
F[status] = ret;
return ret;
}
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
p = price;
ne = needs;
//填充满6
for(int i = price.size(); i <= 6; i++)
{
p.push_back(0);
ne.push_back(0);
}
//将个数和价格分离
for(auto &i : special)
{
vector<int> item;
item = i;
item.pop_back();
int money = i[i.size() - 1];
for(int j = item.size(); j <= 6; j++)
item.push_back(0);
spec.push_back({item, money});
}
for(int i = 0; i < 120000; i++)
F[i] = -1;
return dfs(vec2int(ne));
}
};