Permainan Batu II

1140. Permainan Batu II

Kesukaran: Sederhana

Topik: Tatasusunan, Matematik, Pengaturcaraan Dinamik, Jumlah Awalan, Teori Permainan

Alice dan Bob meneruskan permainan mereka dengan timbunan batu. Terdapat beberapa longgokan disusun dalam satu baris, dan setiap longgokan mempunyai nombor integer positif longgokan batu[i]. Objektif permainan ini adalah untuk berakhir dengan batu terbanyak.

Alice dan Bob bergilir-gilir, dengan Alice bermula dahulu. Pada mulanya, M = 1.

Pada giliran setiap pemain, pemain itu boleh mengambil semua batu dalam cerucuk pertama X yang tinggal, dengan 1 <= X <= 2M. Kemudian, kita tetapkan M = maks(M, X).

Permainan diteruskan sehingga semua batu telah diambil.

Dengan mengandaikan Alice dan Bob bermain secara optimum, kembalikan bilangan maksimum batu yang Alice boleh dapat.

Contoh 1:

• Input: buasir = [2,7,9,4,4]
• Output: 10
• Penjelasan: Jika Alice mengambil satu longgokan pada mulanya, Bob mengambil dua longgokan, kemudian Alice mengambil 2 longgokan lagi. Alice boleh mendapat 2 + 4 + 4 = 10 buasir kesemuanya. Jika Alice mengambil dua cerucuk pada mulanya, maka Bob boleh mengambil ketiga-tiga cerucuk yang tinggal. Dalam kes ini, Alice mendapat 2 + 7 = 9 buasir secara keseluruhan. Jadi kami kembalikan 10 kerana ia lebih besar.

Contoh 2:

• Input: buasir = [1,2,3,4,5,100]
• Output: 104

Kekangan:

• 1 <= timbunan.panjang <= 100
• 1 <= buasir[i] <= 10⁴

Petunjuk:

1. Gunakan pengaturcaraan dinamik: keadaan ialah (i, m) untuk jawapan longgokan[i:] dan yang diberi m.

Penyelesaian:

Kita perlu menggunakan pengaturcaraan dinamik untuk mencari bilangan maksimum batu yang Alice boleh dapat jika kedua-dua pemain bermain secara optimum. Berikut ialah pendekatan langkah demi langkah untuk membangunkan penyelesaian:

1. Tentukan Keadaan dan Peralihan:

   • Tentukan tatasusunan DP 2D dengan dp[i][m] mewakili batu maksimum yang Alice boleh kumpul bermula dari longgokan i dengan had pilihan maksimum m.
   • Gunakan tatasusunan jumlah awalan untuk mengira jumlah batu dalam subarray dengan cekap.

2. Kes Asas:

   • Jika tiada batu lagi untuk dipilih, markah ialah 0.

3. Kes Rekursif:

   • Bagi setiap cerucuk i dan maksimum yang dibenarkan memilih m, kira batu maksimum yang Alice boleh kumpulkan dengan mengambil kira semua pergerakan yang mungkin (mengambil 1 hingga 2m cerucuk).

4. Fungsi Peralihan:

   • Untuk setiap kemungkinan bilangan cerucuk yang Alice boleh pilih, kira jumlah batu yang Alice boleh dapat dan gunakan keputusan keadaan masa hadapan untuk memutuskan langkah optimum.

Mari laksanakan penyelesaian ini dalam PHP: 1140. Permainan Batu II

stoneGameII($piles1) . "\n"; // Output: 10
echo $solution->stoneGameII($piles2) . "\n"; // Output: 104
?>






  
  
  Penjelasan:




Pengiraan Jumlah Awalan: Ini membantu dalam pengiraan cepat jumlah batu daripada mana-mana longgokan i hingga j.

Permulaan Tatasusunan DP: dp[i][m] memegang batu maksimum yang Alice boleh dapat bermula dari longgokan i dengan had pilihan maksimum m.

Peralihan Pengaturcaraan Dinamik: Untuk setiap longgokan dan m, kira batu maksimum yang Alice boleh kumpulkan dengan mengulang kemungkinan kiraan longgokan yang dia boleh ambil dan mengemas kini tatasusunan DP dengan sewajarnya.


Pendekatan ini memastikan penyelesaian dikira dengan cekap, mengambil kesempatan daripada pengaturcaraan dinamik untuk mengelakkan pengiraan berlebihan.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci Permainan Batu II. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!