สมมุติว่าในเกมที่ชื่อว่า "100 เกม" ผู้เล่นสองคนผลัดกันบวกกับจำนวนเต็มใดๆ จาก 1 ถึง 10 ผู้เล่นที่ทำให้ยอดรวมวิ่งเป็นคนแรกหรือ เกิน 100 เขา / เธอชนะ แล้วถ้าเราเปลี่ยนเกมไม่ให้ผู้เล่นใช้จำนวนเต็มซ้ำล่ะ
ตัวอย่างเช่น หากผู้เล่นสองคนผลัดกันดึงจากกลุ่มตัวเลขทั่วไปที่ 1..15 โดยไม่มีการเปลี่ยนจนกว่าจะถึงยอดรวม>=100
ดังนั้น สมมติว่าให้จำนวนเต็ม maxChoosableInteger และจำนวนเต็มอื่นที่ต้องการ ให้พิจารณาว่าผู้เล่นคนแรกที่ย้ายสามารถบังคับให้ชนะ สมมติว่าผู้เล่นทั้งสองเล่นอย่างเหมาะสมที่สุด
เราสามารถสมมติได้เสมอว่า maxChoosableInteger จะไม่มากกว่าค่า 20 และผลรวมที่ต้องการจะไม่เกิน 300 ดังนั้นหากอินพุตคือ maxChooseableInteger =20 และผลรวมที่ต้องการคือ 11 ดังนั้น ผลลัพธ์จะเป็นเท็จ ไม่ว่าผู้เล่นคนแรกจะเลือกใคร ผู้เล่นคนแรกก็จะแพ้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สร้างอาร์เรย์ชื่อ dp ขนาด 2^21
-
กำหนดวิธีการแก้ปัญหา () ซึ่งจะใช้เวลา n, s และมาสก์
-
ถ้า s <=0 ให้คืนค่าเท็จ
-
ถ้า dp[mask] ไม่ใช่ -1 ให้คืนค่า dp[mask]
-
set ret :=false
-
สำหรับฉันอยู่ในช่วง 1 ถึง n
-
ถ้า (เปลี่ยนหน้ากากฉันกัดไปทางขวา) เป็นเลขคี่
-
ret :=ret OR (ผกผันของ Solve(n, s – i, mask XOR 2^i))
-
-
-
dp[mask] :=ยกเลิก
-
รีเทิร์น
-
จากวิธีหลัก ให้ทำดังนี้
-
ถ้าต้องการรวม <=0 แล้วคืนค่าจริง
-
สำหรับผมอยู่ในช่วง 0 ถึง 2^21
-
dp[i] :=-1
-
-
หากต้องการทั้งหมด> (ผลรวมของตัวเลข n ตัวแรก) ให้คืนค่าเท็จ
-
กลับแก้(n, ที่ต้องการรวม, 0)
ตัวอย่าง (C++)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int dp[1 << 21];
bool solve(int n, int s, int mask){
if(s <= 0) return false;
if(dp[mask] != -1) return dp[mask];
bool ret = false;
for(int i = 1; i <= n; i++){
if(!((mask >> i) & 1)){
ret |= (!solve(n, s - i, (mask ^ (1 << i))));
}
}
return dp[mask] = ret;
}
bool canIWin(int n, int desiredTotal) {
if(desiredTotal <= 0) return true;
for(int i = 0; i < (1 << 21); i++)dp[i] = -1;
if(desiredTotal > (n * (n + 1)/ 2))return false;
return solve(n, desiredTotal, 0);
}
};
main() {
Solution ob;
cout << (ob.canIWin(10,11));
} อินพุต
10 11
ผลลัพธ์
0
