两个马匪分金子

2024-05-11 02:18

文章标签 两个金子马匪分

本文主要是介绍两个马匪分金子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解题思路

考虑先手和后手在序列a(1)；a(2);…;a(n)上博弈：
* 如果先手取走了a1，那么问题转为两个人在a(2)；a(3)；…；a(n)上的博弈
* 如果先手取走了an,问题就变为了在a(1)；a(2);…;a(n-1)上的博弈

假设，f(L,R)为两个人在序列a(L);a(L+1);…a(R)上博弈时，先手最多能拿到多少价值，此时后手拿到的
价值一定为:

总价值-f(L,R)

代码

非递归版本动态规划求解

int dp[555][555];
int sum[555];
int main(int argc, char* argv[])
{int nums = 0;while (cin >> nums){if (nums > 0){/*nums组测试数据*/for (int i = 0; i < nums; i++){int numsofdata;//一组数据的个数int input;int aValue = 0,bValue = 0;vector<int> ivec;cin >> numsofdata;for (int j = 0; j < numsofdata; j++){cin >> input;ivec.push_back(input);}if (ivec.size() != numsofdata)throw exception("Invalid Input");for (size_t k = 1; k <= ivec.size(); k++)sum[k] = sum[k-1]+ivec[k-1];for (int z = 1; z <= numsofdata; z++)dp[z][z] = ivec[z-1];for (int m = 1; m <= numsofdata - 1; m++){for (int n = 1; n + m <= numsofdata; n++){dp[n][n + m] = sum[n + m] - sum[n - 1] - min(dp[n][n + m - 1], dp[n + 1][n + m]);}}aValue = dp[1][numsofdata];cout << "Case # " << i + 1 << ":" << aValue << " " << sum[numsofdata] - aValue << endl;}}}

递归版本动态规划求解

int getGolds(vector<int>& golds, int sum)
{
#define MIN(a,b) (((a)>(b))?(b):(a))if (golds.size() == 1)return golds[0];int leftNum = golds[0];vector<int> goldsLeft(golds.begin() + 1, golds.end());int rightNum = golds[golds.size() - 1];vector<int> goldsRight(golds.begin(), golds.end() - 1);return sum - MIN(getGolds(goldsLeft, sum - leftNum), getGolds(goldsRight, sum - rightNum));}