Stone Game III trong C++

Amal và Bimal chơi game lấy đá: hàng đá có giá trị stoneValue[i]. Mỗi lượt lấy 1-3 viên từ đầu. Điểm = tổng giá trị lấy được. Ai điểm cao hơn thắng. Cả hai chơi tối ưu. Trả về "Amal", "Bimal" hoặc "Tie".

Ví dụ: [1,2,3,7] → Bimal thắng (Amal lấy 3 viên = 6, Bimal lấy 7).

Giải thuật (DP từ cuối)

DP[i] = chênh lệch điểm tối đa người hiện tại có thể đạt từ vị trí i. DP[i] = max(sum[i..i+k-1] - DP[i+k]) với k=1..3. sum[i] = tổng từ i đến cuối.

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string stoneGameIII(vector<int>& v) {
        int n = v.size();
        vector<int> dp(n + 1, -1e9), sum(n + 1, 0);
        for (int i = n - 1; 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 amal = dp[0];
        int bimal = total - amal;
        
        if (amal > bimal) return "Amal";
        if (amal == bimal) return "Tie";
        return "Bimal";
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,3,7};
    cout << ob.stoneGameIII(v); // Bimal
    return 0;
}

Đầu vào / Đầu ra

Input: {1,2,3,7}
Output: Bimal