数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学C++程序：求解位移除游戏的最大得分
假设我们有一个包含n位的二进制字符串S。Amal和Bimal正在玩一个游戏。Amal先走，然后是Bimal，他们轮流移动。在他们的移动过程中，玩家可以选择S中任意数量（不少于一个）连续相等的字符并将其移除。移除字符后，移除块左侧和右侧的字符会相邻。当字符串变为空时，游戏结束，每个玩家的分数将是他们删除的1字符的数量。他们都想最大化自己的分数。我们必须找到Amal的最终得分。
问题类别
为了解决这个问题，我们需要操作字符串。编程语言中的字符串是存储在特定数组式数据类型中的字符流。几种语言将字符串指定为特定数据类型（例如Java、C++、Python）；而其他几种语言则将字符串指定为字符数组（例如C）。字符串在编程中非常重要，因为它们通常是各种应用程序中首选的数据类型，并用作输入和输出的数据类型。有各种字符串操作，例如字符串搜索、子串生成、字符串剥离操作、字符串转换操作、字符串替换操作、字符串反转操作等等。查看下面的链接，了解如何在C/C++中使用字符串。
https://tutorialspoint.com/cplusplus/cpp_strings.htm
https://tutorialspoint.com/cprogramming/c_strings.htm
因此，如果我们问题的输入类似于S = "01111001"，则输出将为4。
步骤
为了解决这个问题，我们将遵循以下步骤：
n := size of S Define an array c of size: 150 and filled with 0 num := 0 c1 := 0 for initialize i := 0, when i < n, update (increase i by 1), do: if S[i] is same as '1', then: (increase num by 1) Otherwise c[c1] := num increase c1 by 1 num := 0 c[c1] := num and increase c1 by 1 sort the array c up to next c1 positions sum := 0 for initialize i := c1 - 1, when i >= 0, update i = i - 2, do: sum := sum + c[i] return sum
示例
让我们看看下面的实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
int solve(string S){
int n = S.size();
int c[150] = { 0 };
int num = 0;
int c1 = 0;
for (int i = 0; i < n; i++){
if (S[i] == '1')
num++;
else{
c[c1++] = num;
num = 0;
}
}
c[c1++] = num;
sort(c, c + c1);
int sum = 0;
for (int i = c1 - 1; i >= 0; i = i - 2){
sum = sum + c[i];
}
return sum;
}
int main(){
string S = "01111001";
cout << solve(S) << endl;
}输入
"01111001"
输出
4
更新于：2022年4月8日
浏览量：121
广告