C ++中的石头游戏

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有两个玩家Alex和Lee，他们玩着一堆堆石头。偶数排成一排，每堆有一定数量的石堆[i]。游戏的目标是以最多的石头结束。当石头总数为奇数时，就没有关系了。亚历克斯和李轮流转，亚历克斯先发。在每个回合中，玩家从该行的开头或结尾拿走整堆石头。这将继续进行直到没有更多的桩剩下了，这时拥有最多石头的人获胜。假设亚历克斯和李扮演最佳状态，请检查亚历克斯是否赢得比赛。因此，如果输入像[5,3,4,5]，那么结果将为true，因为Alex首先开始，所以他只能取前5个或后5个。现在，如果他取前5个，那么该行变为[3，4，5]。如果Lee在那之后拿3，则局是[4，5]，而Alex以5赢得10分。当Lee拿到最后5时，局面是[3，4]，Alex拿4赢得9分。因此，这表明前5名是Alex的胜利之举，答案是正确的。

为了解决这个问题，我们将遵循以下步骤-

  • n：=桩阵列的大小

  • 创建大小为nxn的矩阵dp，创建另一个大小为n + 1的数组pre

  • 对于i，范围为0至n – 1

    • pre [i + 1]：= pre [i] +桩[i]

  • 对于2到n之间的l-

    • dp [i，j]：=桩[j] + pre [j] – pre [i] – dp [i，j – 1]和桩[i] + pre [i + 2] – pre [j]的最大值+ dp [i + 1，j]

    • 对于i：= 0，j：= l – 1，j <n，将i和j加1

  • 当dp [0，n – 1]> dp [0，n – 1] – pre [n]时返回true

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool stoneGame(vector<int>& piles) {
      int n = piles.size();
      vector < vector <int> > dp(n,vector <int>(n));
      vector <int> pre(n + 1);
      for(int i = 0; i < n; i++){
         pre[i + 1] = pre[i] + piles[i];
      }
      for(int l = 2; l <= n; l++){
         for(int i = 0, j = l - 1; j < n; i++, j++){
            dp[i][j] = max(piles[j] + pre[j] - pre[i] - dp[i][j - 1], piles[i] + pre[i + 2] - pre[j] +             dp[i       + 1][j]);
         }
      }
      return dp[0][n - 1] > dp[0][n - 1] - pre[n];
   }
};
main(){
   vector<int> v = {5,3,4,5};
   Solution ob;
   cout << (ob.stoneGame(v));
}

输入项

[5,3,4,5]

输出结果

1

以上是 C ++中的石头游戏 的全部内容， 来源链接： utcz.com/z/317108.html

回到顶部