C++前缀和算法的应用:石头游戏 VIII 原理源码测试用例

2023-10-24 13:28

本文主要是介绍C++前缀和算法的应用:石头游戏 VIII 原理源码测试用例,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文涉及的基础知识点

C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

题目

Alice 和 Bob 玩一个游戏,两人轮流操作, Alice 先手 。
总共有 n 个石子排成一行。轮到某个玩家的回合时,如果石子的数目 大于 1 ,他将执行以下操作:
选择一个整数 x > 1 ,并且 移除 最左边的 x 个石子。
将 移除 的石子价值之 和 累加到该玩家的分数中。
将一个 新的石子 放在最左边,且新石子的值为被移除石子值之和。
当只剩下 一个 石子时,游戏结束。
Alice 和 Bob 的 分数之差 为 (Alice 的分数 - Bob 的分数) 。 Alice 的目标是 最大化 分数差,Bob 的目标是 最小化 分数差。
给你一个长度为 n 的整数数组 stones ,其中 stones[i] 是 从左边起 第 i 个石子的价值。请你返回在双方都采用 最优 策略的情况下,Alice 和 Bob 的 分数之差 。
示例 1:
输入:stones = [-1,2,-3,4,-5]
输出:5
解释:

  • Alice 移除最左边的 4 个石子,得分增加 (-1) + 2 + (-3) + 4 = 2 ,并且将一个价值为 2 的石子放在最左边。stones = [2,-5] 。
  • Bob 移除最左边的 2 个石子,得分增加 2 + (-5) = -3 ,并且将一个价值为 -3 的石子放在最左边。stones = [-3] 。
    两者分数之差为 2 - (-3) = 5 。
    示例 2:
    输入:stones = [7,-6,5,10,5,-2,-6]
    输出:13
    解释:
  • Alice 移除所有石子,得分增加 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 ,并且将一个价值为 13 的石子放在最左边。stones = [13] 。
    两者分数之差为 13 - 0 = 13 。
    示例 3:
    输入:stones = [-10,-12]
    输出:-22
    解释:
  • Alice 只有一种操作,就是移除所有石子。得分增加 (-10) + (-12) = -22 ,并且将一个价值为 -22 的石子放在最左边。stones = [-22] 。
    两者分数之差为 (-22) - 0 = -22 。
    参数范围:
    n == stones.length
    2 <= n <= 105
    -104 <= stones[i] <= 104

分析

思路

dp[i]表示剩余i个石头时,(先手方分数-后手方分数)的最大值。计算dp[i]时,假定移除石头后,还剩j个,也就是总共(包括之前移除)移除m_c-j个。至少移除一个旧石头,故j的取值范围[0,i) 。cur = stones[0,m_c-j)个石头的价值和 - dp[j]。dp[i]等于cur的最大值。

x > 1

初始状态下,只能移除2个,不能移除1个。
非初始状态下,由于必定会移除新石头,所以移除一个旧石头就可以了。
也就是dp[m_c]时m_c-j不能等于1,也就是j不能m_c-1。j无此限制的取值范围是[0,m_c),加上此限制后就变成[0,m_c-1),即i < m_c-1

注意

题意:包括新石头,只剩一个石头的时候结束。我的理解:不包括新石头,没石头的时候结束。初始状态外,一定有新石头,所以两种等价。初始状态,且石头大于1时,两者等价,都是未结束。一个石头,两者不等价。但本题石头数>=2。所以在本题范围内等价。

怀疑

这个题目可能出错了,可能是不放新石头。这样需要技巧合并i。

代码

错误代码

错误原因:忽略了x>1。
class Solution {
public:
int stoneGameVIII(vector& stones) {
m_c = stones.size();
vector dp(m_c + 1);//dp[i]表示剩余i个石头时,(先手方分数-后手方分数)的最大值
//计算dp[i]时,假定移除石头后,还剩j个,也就是移除m_c-j个
// cur = stones[0,m_c-j)个石头的价值和 - dp[j]
vector vSum = { 0 };
for (const auto& n : stones)
{
vSum.emplace_back(n + vSum.back());
}
int iMax = vSum[m_c - 0]-dp[0];
for (int i = 1; i <= m_c; i++)
{
dp[i] = iMax;
iMax = max(iMax, vSum[m_c - i] - dp[i]);
}
return dp.back();
}
int m_c;
};

修正缺陷后

解决方法

class Solution {
public:int stoneGameVIII(vector<int>& stones) {m_c = stones.size();//dp[i]表示剩余i个石头时,(先手方分数-后手方分数)的最大值m_dp.resize(m_c + 1);//计算dp[i]时,假定移除石头后,还剩j个,也就是移除m_c-j个// j的取值范围[0,i) 且m_c-j>1// cur = stones[0,m_c-j)个石头的价值和 - dp[j]vector<int> vSum = { 0 };for (const auto& n : stones){vSum.emplace_back(n + vSum.back());}int iMax = vSum[m_c - 0]-m_dp[0];for (int i = 1; i <= m_c; i++){m_dp[i] = iMax;if (m_c - i > 1){iMax = max(iMax, vSum[m_c - i] - m_dp[i]);}}return m_dp.back();}int m_c;vector<int> m_dp;//dp[i]表示剩余i个石头时,(先手方分数-后手方分数)的最大值
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

int main()
{
Solution slu;
vector stones;
int res = 0;
stones = { -1, 2, -3, 4, -5, 6 };
res = slu.stoneGameVIII(stones);
Assert(3, res);
Assert(vector{0, 3, 3, 3, 3, 3, 3}, slu.m_dp);
stones = { -3,-5,3 };
res = slu.stoneGameVIII(stones);
Assert(-3, res);
Assert(vector{0, -5,-3,-3}, slu.m_dp);
stones = { -1, 2, -3, 4, -5 };
res = slu.stoneGameVIII(stones);
Assert(5, res);
Assert(vector{0, -3, 5, 5, 5, 5}, slu.m_dp);
stones = { -10,-12 };
res = slu.stoneGameVIII(stones);
Assert(-22, res);
Assert(vector{0, -22,-22}, slu.m_dp);

//CConsole::Out(res);

}

2023年2月旧代码

class Solution {
public:
int stoneGameVIII(vector& stones) {
m_c = stones.size();
vector preSum;
int iSum = 0;
for (const auto& s : stones)
{
iSum += s;
preSum.push_back(iSum);
}
vector dp(m_c);
dp.back() = preSum.back();
for (int i = m_c - 2; i >= 1; i–)
{
dp[i] = max(dp[i + 1], preSum[i] - dp[i + 1]);
}
return dp[1];
}
int m_c;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

| 鄙人想对大家说的话
|
|-|
|闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。|
| 墨家名称的来源:有所得以墨记之。 |
|如果程序是一条龙,那算法就是他的是睛|

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17

这篇关于C++前缀和算法的应用:石头游戏 VIII 原理源码测试用例的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/275461

相关文章

Spring 中 BeanFactoryPostProcessor 的作用和示例源码分析

《Spring中BeanFactoryPostProcessor的作用和示例源码分析》Spring的BeanFactoryPostProcessor是容器初始化的扩展接口,允许在Bean实例化前... 目录一、概览1. 核心定位2. 核心功能详解3. 关键特性二、Spring 内置的 BeanFactory

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

VSCode中C/C++编码乱码问题的两种解决方法

《VSCode中C/C++编码乱码问题的两种解决方法》在中国地区,Windows系统中的cmd和PowerShell默认编码是GBK,但VSCode默认使用UTF-8编码,这种编码不一致会导致在VSC... 目录问题方法一:通过 Code Runner 插件调整编码配置步骤方法二:在 PowerShell

C/C++随机数生成的五种方法

《C/C++随机数生成的五种方法》C++作为一种古老的编程语言,其随机数生成的方法已经经历了多次的变革,早期的C++版本使用的是rand()函数和RAND_MAX常量,这种方法虽然简单,但并不总是提供... 目录C/C++ 随机数生成方法1. 使用 rand() 和 srand()2. 使用 <random

JAVA封装多线程实现的方式及原理

《JAVA封装多线程实现的方式及原理》:本文主要介绍Java中封装多线程的原理和常见方式,通过封装可以简化多线程的使用,提高安全性,并增强代码的可维护性和可扩展性,需要的朋友可以参考下... 目录前言一、封装的目标二、常见的封装方式及原理总结前言在 Java 中,封装多线程的原理主要围绕着将多线程相关的操

Java逻辑运算符之&&、|| 与&、 |的区别及应用

《Java逻辑运算符之&&、||与&、|的区别及应用》:本文主要介绍Java逻辑运算符之&&、||与&、|的区别及应用的相关资料,分别是&&、||与&、|,并探讨了它们在不同应用场景中... 目录前言一、基本概念与运算符介绍二、短路与与非短路与:&& 与 & 的区别1. &&:短路与(AND)2. &:非短

kotlin中的模块化结构组件及工作原理

《kotlin中的模块化结构组件及工作原理》本文介绍了Kotlin中模块化结构组件,包括ViewModel、LiveData、Room和Navigation的工作原理和基础使用,本文通过实例代码给大家... 目录ViewModel 工作原理LiveData 工作原理Room 工作原理Navigation 工

Java的volatile和sychronized底层实现原理解析

《Java的volatile和sychronized底层实现原理解析》文章详细介绍了Java中的synchronized和volatile关键字的底层实现原理,包括字节码层面、JVM层面的实现细节,以... 目录1. 概览2. Synchronized2.1 字节码层面2.2 JVM层面2.2.1 ente

Win32下C++实现快速获取硬盘分区信息

《Win32下C++实现快速获取硬盘分区信息》这篇文章主要为大家详细介绍了Win32下C++如何实现快速获取硬盘分区信息,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实现代码CDiskDriveUtils.h#pragma once #include <wtypesbase

MySQL的隐式锁(Implicit Lock)原理实现

《MySQL的隐式锁(ImplicitLock)原理实现》MySQL的InnoDB存储引擎中隐式锁是一种自动管理的锁,用于保证事务在行级别操作时的数据一致性和安全性,本文主要介绍了MySQL的隐式锁... 目录1. 背景:什么是隐式锁?2. 隐式锁的工作原理3. 隐式锁的类型4. 隐式锁的实现与源代码分析4