638. 大礼包

ops/2024/11/20 4:34:01/

638. 大礼包


题目链接:638. 大礼包

代码如下:

class Solution 
{
public:int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {//过滤不需要计算的大礼包,只保留需要计算的大礼包vector<vector<int>> filterSpecial;for (auto& sp : special){int totalCount = 0, totalPrice = 0;for (int i = 0; i < price.size(); i++){totalCount += sp[i];totalPrice += sp[i] * price[i];}if (totalCount > 0 && totalPrice > sp[price.size()]){filterSpecial.emplace_back(sp);}}return dfs(price, special, needs, filterSpecial, price.size());}private:map<vector<int>, int> memo;//记忆化搜索计算满足购物清单所需花费的最低价格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];}
};

http://www.ppmy.cn/ops/135149.html

相关文章

websocket身份验证

websocket身份验证 前言 上一集我们就完成了websocket初始化的任务&#xff0c;那么我们完成这个内容之后就应该完成一个任务&#xff0c;当客户端与服务端连接成功之后&#xff0c;客户端应该主动发起一个身份认证的消息。 身份认证proto 我们看一眼proto文件的内容。 我…

git相关知识

前言&#xff1a;在学习git之前首先需要了解几个概念&#xff1a;工作区&#xff0c;暂存区&#xff0c;版本库。 工作区&#xff1a;是电脑上写代码或者文件的目录。 暂存区&#xff1a;一般存放在.git目录下的index中&#xff0c;也称索引。&#xff08;git add&#xff09…

Executor和Service

Executor和Service是Android开发中两个重要的概念&#xff0c;它们都用于处理后台任务&#xff0c;但有着不同的用途和特点。让我们来详细比较一下&#xff1a; 1. Executor&#xff08;执行器&#xff09;&#xff1a; 定义&#xff1a;Executor是一个接口&#xff0c;用于管…

Windows系统 ElasticSearch,分词器、Kibana安装

目录 1.wins安装ElasticSearch1.下载es安装包2.下载分词器3.注意事项4.学会看报错日志 2.将 elasticsearch 以服务的方式安装安装ES解压到根盘符下&#xff0c;如C或E盘等&#xff0c;因为 E:\Program Files文件夹下的都是默认的只读权限&#xff0c;所以换到没有只读权限&…

SPIRiT-Diffusion:基于自一致性驱动的加速MRI扩散模型|文献速递-基于深度学习的病灶分割与数据超分辨率

Title 题目 SPIRiT-Diffusion: Self-Consistency Driven Diffusion Model for Accelerated MRI SPIRiT-Diffusion&#xff1a;基于自一致性驱动的加速MRI扩散模型 01 文献速递介绍 磁共振成像&#xff08;MRI&#xff09; 在临床和研究领域被广泛应用。然而&#xff0c;其…

GPT-5 要来了:抢先了解其创新突破

Microsoft 的工程师计划于 2024 年 11 月在 Azure 上部署 Orion (GPT-5)。虽然这一版本不会向公众开放&#xff0c;但其上线被视为人工智能领域的一个重要里程碑&#xff0c;并将产生深远的影响。 文章目录 GPT-5 真的要来了GPT-4 的局限性GPT-5 的创新突破与遗留挑战GPT-5 预期…

【机器学习】机器学习中用到的高等数学知识-1.线性代数 (Linear Algebra)

向量(Vector)和矩阵(Matrix)&#xff1a;用于表示数据集&#xff08;Dataset&#xff09;和特征&#xff08;Feature&#xff09;。矩阵运算&#xff1a;加法、乘法和逆矩阵(Inverse Matrix)等&#xff0c;用于计算模型参数。特征值(Eigenvalues)和特征向量(Eigenvectors)&…

掌握ECMAScript模块化:构建高效JavaScript应用

标题&#xff1a;掌握ECMAScript模块化&#xff1a;构建高效JavaScript应用 在现代JavaScript开发中&#xff0c;模块化编程已经成为一个不可或缺的概念。它帮助我们管理和组织代码&#xff0c;提高代码的复用性和可维护性。本文将深入探讨ECMAScript模块化的实现&#xff0c;…