สมมุติว่า Amal และ Bimal กำลังเล่นกองหิน มีหินหลายก้อนเรียงเป็นแถว และหินแต่ละก้อนมีค่าที่เกี่ยวข้องกัน ซึ่งเป็นตัวเลขที่ระบุในอาร์เรย์ที่เรียกว่า stoneValue
Amal และ Bimal ผลัดกัน Amal เริ่มก่อน ในเทิร์นของผู้เล่นแต่ละคน เขา/เธอสามารถรับหินได้ 1, 2 หรือ 3 ก้อนจากหินก้อนแรกที่เหลืออยู่ในแถว
คะแนนของผู้เล่นแต่ละคนคือผลรวมของมูลค่าของหินที่ได้มา เริ่มแรกคะแนนคือ 0 เป้าหมายของเกมคือการจบด้วยคะแนนสูงสุดและผู้ชนะคือผู้เล่นที่มีคะแนนสูงสุดและอาจเสมอกัน เกมจะดำเนินต่อไปจนกว่าหินทั้งหมดจะถูกยึดไป
เราจะถือว่า Amal และ Bimal กำลังเล่นได้ดีที่สุด เราต้องคืน "Amal" ถ้า Amal ชนะ "Bimal" ถ้า Bimal ชนะ หรือ "Tie" ถ้าจบเกมด้วยคะแนนเท่ากัน
ดังนั้น หากอินพุตมีค่าเท่ากับ =[1,2,3,7] เอาต์พุตจะเป็น Bimal เนื่องจาก Amal จะสูญเสียเสมอ ท่าที่ดีที่สุดของเขาคือเก็บสามกองและคะแนนกลายเป็น 6 ตอนนี้คะแนนของ Bimal คือ 7 และ Bimal ชนะ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดอาร์เรย์ dp ขนาด n + 10
-
กำหนดผลรวมอาร์เรย์ของขนาด n + 10
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
dp[i] :=-(1^9)
-
-
ผลรวม[n - 1] =v[n - 1]
-
สำหรับการเริ่มต้น i :=n - 2 เมื่อ i>=0, อัปเดต (ลด i โดย 1) ให้ทำ -
-
sum[i] :=sum[i + 1] + v[i]
-
-
สำหรับการเริ่มต้น i :=n - 1 เมื่อ i>=0, อัปเดต (ลด i โดย 1) ให้ทำ -
-
สำหรับการเริ่มต้น k :=i + 1 เมื่อ k <=i + 3 และ k <=n อัปเดต (เพิ่ม k ขึ้น 1) ทำ −
-
dp[i] :=สูงสุดของ dp[i] และ sum[i] - dp[k]
-
-
-
รวม :=sum[0]
-
x :=dp[0]
-
y :=ทั้งหมด - x
-
return x> y เป็นจริง จากนั้น "Amal" :ถ้า x และ y เหมือนกันแล้ว "Tie" มิฉะนั้น "Bimal"
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string stoneGameIII(vector<int>& v) {
int n = v.size();
vector <int> dp(n + 10);
vector <int> sum(n + 10);
for(int i = 0; i < n; i++)dp[i] = -1e9;
sum[n - 1] = v[n - 1];
for(int i = n - 2; i >= 0; i--)sum[i] = sum[i + 1] + v[i];
for(int i = n- 1 ; i >= 0; i--){
for(int k = i + 1; k <= i + 3 && k <= n; k++){
dp[i] = max(dp[i], sum[i] - dp[k]);
}
}
int total = sum[0];
int x = dp[0];
int y = total - x;
return x > y? "Amal" : x == y ? "Tie" : "Bimal";
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,7};
cout << (ob.stoneGameIII(v));
} อินพุต
{1,2,3,7} ผลลัพธ์
Bimal
