ARST打卡第129周[129/521]

Algorithm

lc_638 大礼包

链接:https://leetcode-cn.com/problems/shopping-offers/solution/da-li-bao-by-leetcode-solution-p1ww/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
map<vector<int>, int> memo;

int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
int n = price.size();

// 过滤不需要计算的大礼包,只保留需要计算的大礼包
vector<vector<int>> filterSpecial;
for (auto & sp : special) {
int totalCount = 0, totalPrice = 0;
for (int i = 0; i < n; ++i) {
totalCount += sp[i];
totalPrice += sp[i] * price[i];
}
if (totalCount > 0 && totalPrice > sp[n]) {
filterSpecial.emplace_back(sp);
}
}

return dfs(price, special, needs, filterSpecial, n);
}

// 记忆化搜索计算满足购物清单所需花费的最低价格
int dfs(vector<int> price,const vector<vector<int>> & special, vector<int> curNeeds, vector<vector<int>> & filterSpecial, int n) {
if (!memo.count(curNeeds)) {
int minPrice = 0;
for (int i = 0; i < n; ++i) {
minPrice += curNeeds[i] * price[i]; // 不购买任何大礼包,原价购买购物清单中的所有物品
}
for (auto & curSpecial : filterSpecial) {
int specialPrice = curSpecial[n];
vector<int> nxtNeeds;
for (int i = 0; i < n; ++i) {
if (curSpecial[i] > curNeeds[i]) { // 不能购买超出购物清单指定数量的物品
break;
}
nxtNeeds.emplace_back(curNeeds[i] - curSpecial[i]);
}
if (nxtNeeds.size() == n) { // 大礼包可以购买
minPrice = min(minPrice, dfs(price, special, nxtNeeds, filterSpecial, n) + specialPrice);
}
}
memo[curNeeds] = minPrice;
}
return memo[curNeeds];
}
};

Review

【TED演讲】休假的力量:我为什么要给自己放个长假?

确实,我们可以把退休生活的那几年提取出来,然后分散到我们的工作年中,让自己工作一段时间后,
有一个长长的假期停下来思考思考,自己到底想要什么,做做自己感兴趣的事情,然后让自己充满力量

Tips

gcc编译工具生成动态库和静态库介绍

C语言中,隐藏结构体的细节

Share

2021.1024程序员节快乐

(因为感冒,在家休息了一天,一定要注意身体)

所以这周的分享只有一个:(想偷懒???)

身体是革命的本钱,一定要记得每周锻炼,保持身体健康,精力旺盛