เกมสโตนใน C ++

สมมติว่าเรามีผู้เล่นสองคน อเล็กซ์และลี พวกเขาเล่นเกมกับกองหิน มีกองหินจำนวนเท่ากันที่จัดเรียงเป็นแถว และแต่ละกองมีกองหินจำนวนหนึ่ง[i] วัตถุประสงค์ของเกมคือการจบด้วยหินมากที่สุด เมื่อจำนวนหินทั้งหมดเป็นเลขคี่ จะไม่มีความสัมพันธ์กัน อเล็กซ์และลีผลัดกัน โดยที่อเล็กซ์เริ่มก่อน ในแต่ละเทิร์น ผู้เล่นจะหยิบก้อนหินทั้งกองจากจุดเริ่มต้นหรือจุดสิ้นสุดของแถว นี้จะดำเนินต่อไปจนกว่าจะไม่มีกองเหลือซึ่งจุดที่ผู้ที่มีก้อนหินมากที่สุดจะเป็นผู้ชนะ สมมติว่า Alex และ Lee เล่นได้ดีที่สุด ตรวจสอบว่า Alex ชนะเกมหรือไม่ ดังนั้นหากอินพุตเป็น [5,3,4,5] ผลลัพธ์จะเป็นจริง อย่างที่อเล็กซ์เริ่มก่อน เขารับได้เพียง 5 ตัวแรกหรือ 5 ตัวสุดท้าย ตอนนี้ถ้าเขารับ 5 ตัวแรก ดังนั้น ที่แถวจะกลายเป็น [3, 4, 5] ถ้า Lee ได้ 3 แต้มหลังจากนั้น บอร์ดก็จะเป็น [4, 5] และ Alex ได้ 5 แต้มเพื่อให้ได้ 10 แต้ม เมื่อลีเข้ารอบ 5 คนสุดท้าย กระดานก็จะเป็น [3, 4] และอเล็กซ์นำ 4 ไปชนะด้วย 9 แต้ม ดังนั้นสิ่งนี้จึงบ่งชี้ว่าการรับ 5 อันดับแรกเป็นการย้ายที่ชนะสำหรับ Alex คำตอบนั้นเป็นจริง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของไพล์อาร์เรย์

• สร้างเมทริกซ์ขนาด dp n x n สร้างอาร์เรย์อื่นที่เรียกว่า pre ของขนาด n + 1

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • pre[i + 1] :=pre[i] + piles[i]

• สำหรับ l ในช่วง 2 ถึง n −

  • สำหรับ i :=0, j :=l – 1, j

    • dp[i, j] :=สูงสุดของ piles[j] + pre[j] – pre[i] – dp[i, j – 1] และ piles[i] + pre[i + 2] – pre[j] + dp[i + 1, j]

• คืนค่าจริงเมื่อ dp[0, n – 1]> dp[0, n – 1] – ก่อน[n]

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool stoneGame(vector<int>& piles) {
      int n = piles.size();
      vector < vector <int> > dp(n,vector <int>(n));
      vector <int> pre(n + 1);
      for(int i = 0; i < n; i++){
         pre[i + 1] = pre[i] + piles[i];
      }
      for(int l = 2; l <= n; l++){
         for(int i = 0, j = l - 1; j < n; i++, j++){
            dp[i][j] = max(piles[j] + pre[j] - pre[i] - dp[i][j - 1], piles[i] + pre[i + 2] - pre[j] +             dp[i       + 1][j]);
         }
      }
      return dp[0][n - 1] > dp[0][n - 1] - pre[n];
   }
};
main(){
   vector<int> v = {5,3,4,5};
   Solution ob;
   cout << (ob.stoneGame(v));
}

อินพุต

[5,3,4,5]

ผลลัพธ์

1