資料結構
網路
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.tw/cplusplus/cpp_strings.htm
https://tutorialspoint.tw/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
廣告