Giả sử Amal và Bimal đang chơi với đống đá. Có một số viên đá được sắp xếp thành một hàng và mỗi viên đá có một giá trị liên quan là một số được cho trong mảng được gọi là stoneValue.
Amal và Bimal thay phiên nhau, với Amal bắt đầu trước. Trên mỗi lượt của người chơi, họ có thể lấy 1, 2 hoặc 3 viên đá từ những viên đá còn lại đầu tiên trong hàng.
Điểm của mỗi người chơi là tổng giá trị của các viên đá lấy được. Ban đầu, số điểm là 0. Mục tiêu của trò chơi là kết thúc với số điểm cao nhất, và người chiến thắng là người chơi có số điểm cao nhất và cũng có thể hòa. Trò chơi tiếp tục cho đến khi tất cả các viên đá được lấy hết.
Chúng tôi sẽ giả định rằng Amal và Bimal đang chơi tối ưu. Chúng ta phải trả về "Amal" nếu Amal thắng, "Bimal" nếu Bimal thắng hoặc "hòa" nếu họ kết thúc trò chơi với cùng số điểm.
Vì vậy, nếu đầu vào là giá trị =[1,2,3,7], thì đầu ra sẽ là Bimal, As Amal sẽ luôn mất. Nước đi tốt nhất của anh ta sẽ là lấy ba cọc và điểm số trở thành 6. Bây giờ điểm số của Bimal là 7 và Bimal thắng.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một mảng dp có kích thước n + 10
-
Xác định tổng mảng có kích thước n + 10
-
để khởi tạo i:=0, khi i
-
dp [i]:=- (1 ^ 9)
-
-
sum [n - 1] =v [n - 1]
-
để khởi tạo i:=n - 2, khi i> =0, cập nhật (giảm i đi 1), thực hiện -
-
sum [i]:=sum [i + 1] + v [i]
-
-
để khởi tạo i:=n - 1, khi i> =0, cập nhật (giảm i đi 1), thực hiện -
-
để khởi tạo k:=i + 1, khi k <=i + 3 và k <=n, cập nhật (tăng k lên 1), thực hiện -
-
dp [i]:=tối đa của dp [i] và sum [i] - dp [k]
-
-
-
tổng:=sum [0]
-
x:=dp [0]
-
y:=tổng - x
-
trả về x> y là true thì "Amal":nếu x và y giống nhau thì "Tie", ngược lại là "Bimal"
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
{1,2,3,7} Đầu ra
Bimal