C语言巨难题:执行操作可获得的最大总奖励 I(C语言版)
1.题目:
给你一个整数数组 rewardValues,长度为 n,代表奖励的值。
最初,你的总奖励 x 为 0,所有下标都是 未标记 的。你可以执行以下操作 任意次 :
- 从区间
[0, n - 1]中选择一个 未标记 的下标i。 - 如果
rewardValues[i]大于 你当前的总奖励x,则将rewardValues[i]加到x上(即x = x + rewardValues[i]),并 标记 下标i。
以整数形式返回执行最优操作能够获得的 最大 总奖励。
示例 1:
输入:rewardValues = [1,1,3,3]
输出:4
解释:
依次标记下标 0 和 2,总奖励为 4,这是可获得的最大值。
示例 2:
输入:rewardValues = [1,6,4,3,2]
输出:11
解释:
依次标记下标 0、2 和 1。总奖励为 11,这是可获得的最大值。
提示:
1 <= rewardValues.length <= 5 * 1041 <= rewardValues[i] <= 5 * 104
该作者解决方法:
不知道C语言要怎么建构bitset,看了其他人的解答后尝试用位运速加速。 假设有一个 bool 数组 dp。在每一次循环中,dp[rewardValues[i] + j] 可以由 dp[j] 转移而来,其中 j 为小于 rewardValues[i] 的非负整数。 为了加速运算并减少空间浪费,可以将 bool 数组改成 unsigned long long。 在C语言中,虽 bool 使用1bit,但最小寻址单位为1字节,所以占用1字节。 现在我们将数组声明成 unsigned long long,此时每次操作最多可以操作64个位元,也就是64个状态。 由于 rewardValues[i] 不一定为64的倍数,为了避免发生溢位的状况,必须将 dp[j] 所代表的64位元拆成两部分。 为了计算正确的下标,我们把 rewardValues[i] 用 index 与 digit 表示,其中 rewardValues[i] = 64 * index + digit:
index = rewardValues[i] / 64
digit = rewardValues[i] % 64
因此,对于每个下标 j,dp[j] 可拆成:
(dp[j] & ((1 << (64 - digit)) - 1)) << digit
dp[j] >> (64 - digit)
假设 rewardValues[i] = 65,那么:
index = 65 / 64 = 1
digit = 65 % 64 = 1
以 dp[0] 的 0 ~ 63 位为例,0 ~ 62 位可以移到 dp[index + 0] 中的 1 ~ 63 位,对应数字 65 ~ 127。而剩下的1个位则放入 dp[index + 1] 的第 0 位,这个过程通过或运算即可。
dp[index + j] |= (dp[j] & ((1 << (64 - digit)) - 1)) << digit;
dp[index + j + 1] |= dp[j] >> (64 - digit);
若 rewardValues[i] 为 64 的倍数可直接转移,不需拆分
代码:
int cmp(const void *a, const void *b)
{return *(int*)a > *(int*)b;
}int maxTotalReward(int* rewardValues, int rewardValuesSize)
{qsort(rewardValues, rewardValuesSize, sizeof(int), cmp);int size = rewardValues[rewardValuesSize - 1] / 32 + 2;unsigned long long dp[size], temp, mask;memset(dp, 0, sizeof(unsigned long long) * size);int index, digit;dp[0] = 1;for (int i = 0; i < rewardValuesSize; ++i) {index = rewardValues[i] / 64;digit = rewardValues[i] % 64;mask = digit ? (1ULL << (64 - digit)) - 1 : 0;for (int j = 0; j < index; ++j){if (digit) {dp[j + index] |= (dp[j] & mask) << digit;dp[j + index + 1] |= dp[j] >> (64 - digit);} else {dp[j + index] |= dp[j];}}if (digit) {temp = dp[index] & ((1ULL << digit) - 1);dp[2 * index] |= (temp & mask) << digit;dp[2 * index + 1] |= temp >> 64 - digit;}}for (int i = size - 1; i >= 0; --i) {if (dp[i])return 64 * i + 63 - __builtin_clzll(dp[i]);}return 0;
}
声明:来源力扣题解
作者:borane
链接:https://leetcode.cn/problems/maximum-total-reward-using-operations-ii/solutions/2805771/01bei-bao-wei-yun-suan-by-modest-nashdn2-svmq/
来源:力扣(LeetCode)
相关文章:
C语言巨难题:执行操作可获得的最大总奖励 I(C语言版)
1.题目: 给你一个整数数组 rewardValues,长度为 n,代表奖励的值。 最初,你的总奖励 x 为 0,所有下标都是 未标记 的。你可以执行以下操作 任意次 : 从区间 [0, n - 1] 中选择一个 未标记 的下标 i。如果…...
【力扣】GO解决子序列相关问题
文章目录 一、引言二、动态规划方法论深度提炼子序列问题的通用解法模式 三、通用方法论应用示例:最长递增子序列(LeetCode题目300)Go 语言代码实现 四、最长连续递增序列(LeetCode题目674)Go 语言代码实现 五、最长重…...
Ubuntu20.04安装VM tools并实现主机和虚拟机之间文件夹共享
1、Ubuntu20.04安装VM tools 参考这个,很详细:Ubuntu 20.04 安装 VMwareTools 教程 2、实现主机与VMware虚拟机共享文件夹 设置共享文件夹参考:windows和虚拟机互传文件的三种方式 挂载操作参考:主机与VMware虚拟机共享文件夹&…...
Linux 学习笔记(十七)—— 文件系统
终极目标:理解 inode 和 软硬连接; 文件系统:Ext2; 文件 文件内容 文件属性; ——> 磁盘上存储的文件 存储的文件内容 存储的文件属性; Linux系统中:文件内容使用数据块存储,文件属性使用inode(固定…...
【计算机网络 - 基础问题】每日 3 题(五十八)
✍个人博客:https://blog.csdn.net/Newin2020?typeblog 📣专栏地址:http://t.csdnimg.cn/fYaBd 📚专栏简介:在这个专栏中,我将会分享 C 面试中常见的面试题给大家~ ❤️如果有收获的话,欢迎点赞…...
Netty入门基础:IO模型中BIO\NIO概念及区别【附演示代码】
文章目录 😀BIO💢实战demo 🌈NIO🏍Buffer核心属性核心方法 🎗Channel🎈Selector核心方法 🧨实战demo 🎨粘包与半包 😀BIO 传统IO模型,同步阻塞,每…...
vue2 使用环境变量
一. 在根目录下创建.env.xxx文件 .env 基础系统变量,无论何种环境,都可使用其中配置的值,其他环境中的变量会覆盖.env中的同名变量。 .env.development 开发环境 .env.production 生产环境 .env.staging 测试环境 二. 内容格式 vue2 使用是以…...
数据预处理
继续提取代码片段: 12. **导入iris数据集并查看前5行数据**: python from sklearn.datasets import load_iris iris load_iris() X iris.data print(iris数据集的维度为:, X.shape) print(iris数据集的前5行数据为:\n, X[:5]) …...
django宠物领养管理系统-计算机毕业设计源码26858
目录 1 绪论 1.1 选题背景与意义 1.2国内外研究现状 1.3论文结构与章节安排 2系统分析 2.1 可行性分析 2.2 系统流程分析 2.2.1 数据流程 3.3.2 业务流程 2.3 系统功能分析 2.3.1 功能性分析 2.3.2 非功能性分析 2.4 系统用例分析 2.5本章小结 3 系统总体设计 3…...
使用TeamViewer远程局域网内的两台电脑
有个场景,有人还不知道TV可以局域网操作,记录一下。 主要就是修改设置,将取消激活改为接受 然后输入受控端的ip即可...
GUI简介、Swing的常用组件、java程序的运行过程、class文件、JAR、runable_jar、双括号初始化
GUI简介 GUI:图形用户界面,在计算机中采用图形的方式显示用户界面 java的GUI开发 AWT:java最早推出的GUI编程开发包,界面风格跟随操作系统SWT:eclipse就是java使用SWT开发的Swing:在AWT的基础上扩充了功能…...
@Autowired和@Resource和getBean()区别
今天遇到一个对我来说很奇葩的错误,我想在Service中注入bean,我这里使用了Autowired和Resource都不能注入,导致初始化失败,使用了getBean()方法就可以注入。从来没有遇到过这个问题。后来我查询了一下,才明白了原理。我…...
Merlion笔记(四):添加一个新的预测模型
文章目录 1 模型配置类2 模型类3 运行模型:一个简单的例子4 可视化5 定量评估6 定义一个基于预测器的异常检测器 本文提供了一个示例,展示如何向 Merlion 添加一个新的预测模型,遵循 CONTRIBUTING.md 中的说明。建议在阅读本篇文章之前,先查…...
【论文阅读】ESRGAN
学习资料 论文题目:增强型超分辨率生成对抗网络(ESRGAN: Enhanced Super-Resolution Generative Adversarial Networks)论文地址:[1809.00219] ESRGAN:增强型超分辨率生成对抗网络代码:xinntao / ESRGAN&am…...
电脑异常情况总结
文章目录 笔记本无症状息屏黑屏 笔记本无症状息屏黑屏 🍎 问题描述: 息屏导致黑屏;依次操作计算机--》右键--》管理--》事件查看器--》Windows日志--》系统;从息屏到异常黑屏之间出现了很多错误,如下:事件…...
[项目详解][boost搜索引擎#1] 概述 | 去标签 | 数据清洗 | scp
目录 一、前言 二、项目的相关背景 三、搜索引擎的宏观原理 四、搜索引擎技术栈和项目环境 五、正排索引 VS 倒排索引--原理 正排索引 分词 倒排索引 六、编写数据去除标签和数据清洗模块 Parser 1.数据准备 parser 编码 1.枚举文件 EnumFile 2.去标签ParseHtml(…...
PL/I语言的起源?有C语言,有B语言和A语言吗?为什么shell脚本最开始可能有#!/bin/bash字样?为什么不支持嵌套注释?
PL/I语言的起源 在20世纪50~60年代,当时主流的编程语言是COBOL/FORTRAN/ALGOL等,IBM想要设计一门通用的编程语言,已有的编程语言无法实现此要求,故想要设计一门新语言,即是PL/I. PL/I是Programming Language/One的缩写…...
gin入门教程(3):创建第一个 HTTP 服务器
首先设置golang github代理,可解决拉取git包的时候,无法拉取的问题: export GOPROXYhttps://goproxy.io再查看自己的go版本: go version我这里的版本是:go1.23.2 linux/arm64 准备工作做好之后就可以进行开发了 3.…...
Vue+ECharts+iView实现大数据可视化大屏模板
Vue数据可视化 三个大屏模板 样式还是比较全的 包括世界地图、中国地图、canvas转盘等 项目演示: 视频: vue大数据可视化大屏模板...
el-table 表格设置必填项
el-table 表格设置必填项 要在 el-table 中集成 el-form 来设置必填项,并进行表单验证,可以使用 Element UI 提供的表单验证功能。下面是一个详细的示例,展示了如何在 el-table 中使用 el-form 来设置必填项,并进行验证。 示例代…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器
拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件: 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...
Vue ③-生命周期 || 脚手架
生命周期 思考:什么时候可以发送初始化渲染请求?(越早越好) 什么时候可以开始操作dom?(至少dom得渲染出来) Vue生命周期: 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...
【UE5 C++】通过文件对话框获取选择文件的路径
目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 ,这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器,右键点击 .uproject 文件,选择 "Generate Visual Studio project files",重…...
Windows 下端口占用排查与释放全攻略
Windows 下端口占用排查与释放全攻略 在开发和运维过程中,经常会遇到端口被占用的问题(如 8080、3306 等常用端口)。本文将详细介绍如何通过命令行和图形化界面快速定位并释放被占用的端口,帮助你高效解决此类问题。 一、准…...
