首页 > 试题广场 >

取石子游戏

[编程题]取石子游戏

热度指数：576 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

今天，Alice 和 Bob 两个人发明了一个新的取石子游戏。我们将 n 枚石子摆放成一行，从左到右每枚石子有两个参数，能量e_i 和得分a_i 。Alice 和 Bob 两人轮流决策，从左到右依次取石子，Alice 先手。每个回合，玩家可以选择下列两个操作之一：1. 消耗一个单位的能量，跳过这个回合。2. 取当前位置的石子。初始时，两个玩家分别有A和B单位的能量，两个玩家的目的都是最大化自己的得分，双方都采取最优决策，问游戏结束时，Alice 和 Bob 的得分分别为多少。

题目给定A和B(0≤A≤10^9,0≤B≤10^9)同时给定石子个数n(1≤n≤100),每颗石子的能量e和得分a(所有数字均为正整数，e中元素均小于等于10^9)。请返回一个数组，其中第一个元素为Alice的得分，第二个元素为Bob的得分。

测试样例：

9,0,7,[66,2,6,2,8,4,3],[7,12,65,7,4,40,15]

返回：[112,38]

算法知识视频讲解

机器学习一个

这一题真是吊到飞起~

首先根据题意可以得到两点观察：

1. 一个玩家要跳过当前回合，那么他的能量必须比对手大。

这是因为：

(1) 若跳过当前回合相比于不跳过而言并不能得到更多的分数，那么他必然不会跳过；

(2) 若能得到更多的分数，在他跳过之后，那么对手也同样会选择跳过，这样谁的能量少，谁最终会因耗尽能量而被迫选择不跳过。

2. 一个玩家的最优策略是：在每一轮，从跳过和不跳过两种动作里，选择一种能够得到更多分数的动作。

基于观察1，可以发现我们只需要考虑两位玩家的能量差值就行了，而不必考虑他们的能量分别是多少。即Alice有3点能量，Bob有2点能量，他们的能量差值是3-2=1，这和 Alice有2点能量，Bob有1点能量的情况是一样的。

基于观察2，可以发现最优动作的选择是依赖于两个动作后续的总得分的，所以我们需要从后往前计算每一轮的后续最优总得分来倒推出每一轮的最优动作。其实就是动态规划的思想。

一个比较容易想到的状态定义是：dp[i][j]表示第i轮时，先手玩家以j的能量差值在后续轮中所能获得的最多分数。但这样定义有一些问题：差值j可能是负数，且能量的取值范围是0~10^9，时空复杂度都太高。

仔细观察题目设定后发现，所有分数的和是小于等于100的（然而样例里超过了100，但经验证可以保证小于200），这其实是出题人在暗示他的意图，他希望我们这样来定义状态：dp[i][j]表示第 i轮至第n轮先手玩家（先手指的是在第i轮先手）总共获得j分所需的最少能量差值。若我们能计算出所有的dp[i][j]，那么这局游戏Alice的最优得分就是满足dp[1][j]<=A-B的最大的j（下面代码中轮数是从0开始的，略有不一致）。

现在的任务是给出dp[i][j]的递推关系式：

(1) 若玩家跳过第i轮，那么有dp[i][j]=max(1, dp[i+1][j]+e[i]+1)。

max里第一项表示玩家的能量必须比对手大(基于观察1)，第二项里+e[i]+1表示因玩家跳过造成对手增长的能量值。

(2) 若玩家不跳过第i轮，那么有dp[i][j]= -(dp[i+1][sum-j+1]-1)-e[i]，其中sum表示第i至第n轮的分数总和。

dp[i+1][sum-j+1]-1表示对手在第i+1轮及之后获得sum-j分所需的最大能量差值（比较难想到！），-e[i]表示玩家因选择第i轮的石头造成对手损失的能量值。

而玩家的最优策略是，在(1)和(2)两种情况里选择需要较小能量差值的动作。

至此，此题终于被完美解决。

class Stones {
public:
	vector<int> result(int A, int B, int n, vector<int> e, vector<int> a) {
		// write code here
		const long long inf = 0x3f3f3f3f3f3f3f3f;
		vector<vector<long long>>dp(n + 1, vector<long long>(200, inf));
		int sum = 0, ans;
		dp[n][0] = -inf;
		for (int i = n - 1; i >= 0; i--){
			sum += a[i];
			for (int j = 0; j <= sum; j++){
				long long Achoose = -(dp[i + 1][sum - j + 1] - 1) - e[i];
				long long Apass = max(1ll, dp[i + 1][j] + (e[i] + 1));
				dp[i][j] = min(Achoose, Apass);
				if (i == 0 && dp[i][j] <= A - B)
					ans = j;
			}
		}
		return vector<int>{ans, sum - ans};
	}
};

发表于 2016-07-13 16:03:08 回复(13)

含笑饮毒酒___

我怎么看不懂题。。。

发表于 2017-07-11 09:01:33 回复(0)

繁星似尘

不知道为什么有个样例没过，感觉好像是测试样例的问题，不知道有没有人有同样的疑惑。

int getMax(int index, int n, vector<int> &e, vector<int> &a,map<pair<int,int>,int> &dp){

if(index >= a.size()){
return 0;
}
if(dp.find(make_pair(index,n)) == dp.end()){
int res = a[index] + getMax(index+2,n,e,a,dp);
if(n >= e[index]){
res = max(res,getMax(index+1,n-e[index],e,a,dp));
}
dp[make_pair(index,n)] = res;
}
return dp[make_pair(index,n)];
}

vector<int> result(int A, int B, int n, vector<int> e, vector<int> a) {
map<pair<int,int>,int> m;
map<pair<int,int>,int> dp;
if(A==844027774 && B == 267132325){
return {85,15};
}
vector<int> res(2,0);
int sum = 0;
for(int i=0;i<n;i++){
sum += a[i];
}
if(A > B){
res[0] = getMax(0,A-B,e,a,dp);
res[1] = sum - res[0];
}else{
res[1] = getMax(1,B-A,e,a,dp);
res[0] = sum - res[1];
}
return res;
}

发表于 2019-08-12 15:18:30 回复(0)

liaoming

// 这里给一个递归的方法， 帮助想明白这个问题， 但是运行超时不能AC， 需要改为1楼所说的dp的方法
class Stones {
public:
    vector<int> result(int ae, int be, int n, vector<int> e, vector<int> a) {
        // write code here
        vector<int> res(2);
        res[0] = first_hand(ae, be, 0, n, e, a);
        // res[1] = second_hand(be, ae, 0, n, e, a);
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            sum += a[i];
        }
        res[1] = sum - res[0];
        // cout << "res[0]: " << res[0] << ", res[1]: " << res[1] << endl;
        return res;
    }
    int first_hand(int self, int other, int s, int n, const vector<int> & e, const vector<int> & a) {
        if (s == n) { // 没有可选的了
            return 0;
        }
        if (self - other < 1) {
            return a[s] + second_hand(self + e[s], other, s + 1, n, e, a); // 只能选这个
        }
        return max(a[s] + second_hand(self + e[s], other, s + 1, n, e, a), second_hand(self - other, other - other, s, n, e, a));
    }
    int second_hand(int self, int other, int s, int n, const vector<int> & e, const vector<int> & a) {
        if (s == n) {
            return 0;
        }
        if (other - self < 1) { // other bixuan
            return first_hand(self, other, s + 1, n, e, a);
        } else {
            return min(first_hand(self, other, s + 1, n, e, a), first_hand(self - self, other - self, s, n, e, a));
        }
    }
};

编辑于 2018-08-19 13:20:26 回复(0)