ARST打卡第129周[129/521]

发表于 分类于 阅读次数：
lc_638 大礼包 【TED演讲】休假的力量：我为什么要给自己放个长假？ gcc编译工具生成动态库和静态库介绍 C语言中，隐藏结构体的细节 1024快乐，身体是革命的本钱，一定要保护好身体

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程序员节快乐

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

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

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