首页 > 其他分享 >2023-07-05：爱丽丝和鲍勃继续他们的石子游戏 许多堆石子 排成一行，每堆都有正整数颗石子 piles[i] 游戏以谁手中的石子最多来决出胜负。 爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，

2023-07-05：爱丽丝和鲍勃继续他们的石子游戏 许多堆石子 排成一行，每堆都有正整数颗石子 piles[i] 游戏以谁手中的石子最多来决出胜负。 爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，

时间：2023-07-05 22:13:13浏览次数：44  
标签：index 鲍勃 piles float64 int 石子 pilesSize 爱丽丝

2023-07-05：爱丽丝和鲍勃继续他们的石子游戏

许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]

游戏以谁手中的石子最多来决出胜负。

爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，M = 1。

在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M

然后，令 M = max(M, X)。

游戏一直持续到所有石子都被拿走。

假设爱丽丝和鲍勃都发挥出最佳水平W

返回爱丽丝可以得到的最大数量的石头。

输入：piles = [2,7,9,4,4]。

输出：10。

答案2023-07-05：

1.算法 stoneGameII1：暴力方法

  • 首先定义函数 stoneGameII1，接收一个石子堆的切片 piles 作为参数，并返回爱丽丝可以得到的最大数量的石头。

  • 在函数 stoneGameII1 中调用函数 first1，并传入初始参数 piles、index=0（表示当前石子堆的索引）、m=1（表示当前的 M 值）。

  • 函数 first1 的作用是计算爱丽丝在当前石子堆的状态下的最优解。如果当前石子堆的索引达到了最后一个位置（即 index == len(piles)），则返回 0（石子已经全部取完）。

  • 否则，初始化变量 best = 0（当前的最优解）和 pre = 0（当前已经取走的石子数量）。

  • 开始一个循环，从当前索引开始遍历石子堆（i = index），并且用变量 j 记录当前取走的石子堆的数量（初始值为 1）。

  • 在循环中，更新变量 pre = pre + piles[i]，即计算当前的已取走的石子数量。

  • 然后，根据当前的石子堆状态以及剩余可取的石子堆的数量（int(math.Max(float64(j), float64(m)))），调用函数 second1，并传入相应的参数，计算爱丽丝在下一轮的最优解。

  • 更新变量 best = int(math.Max(float64(best), float64(pre+second1(piles, i+1, int(math.Max(float64(j), float64(m)))))))，即取当前轮最优解和已取走的石子数量之和的较大值作为当前的最优解。

  • 循环结束后，返回变量 best。

函数 second1 的作用是计算鲍勃在当前石子堆的状态下的最优解，其过程与函数 first1 类似。

  • 首先判断是否遍历到了最后一个石子堆，如果是，则返回 0（石子已全部取走）。
  • 否则，初始化变量 worse = math.MaxInt64（当前的最差解）。
  • 开始一个循环，从当前索引开始遍历石子堆，并用变量 j 记录当前取走的石子堆的数量（初始值为 1）。
  • 在循环中，更新变量 worse = int(math.Min(float64(worse), float64(first1(piles, i+1, int(math.Max(float64(j), float64(m)))))))，即取当前轮最差解和已取走的石子数量之和的较小值作为当前的最差解。
  • 循环结束后，返回变量 worse。

2.算法 stoneGameII2：记忆化搜索

  • 首先定义函数 stoneGameII2，接收一个石子堆的切片 piles 作为参数，并返回爱丽丝可以得到的最大数量的石头。

  • 在函数 stoneGameII2 中，首先初始化变量 n 为石子堆的数量，创建两个二维切片 f 和 s，用于存储记忆化搜索的结果。

  • 利用循环，初始化 f 和 s 的值为 -1。

  • 调用函数 first2，并传入初始参数 piles、index=0（表示当前石子堆的索引）、m=1（表示当前的 M 值）、f 和 s。

  • 函数 first2 的作用是计算爱丽丝在当前石子堆的状态下的最优解，其过程类似函数 first1，但加入了记忆化搜索的机制。

  • 首先判断是否已经计算过该状态的结果，如果是，则直接返回存储的结果 f[index][m]。

  • 否则，继续计算最优解。

  • 在计算过程中，每一轮的最优解都会存储在 f[index][m]，以避免重复计算。

  • 在循环中，需要调用函数 second2，传入相应的参数，计算鲍勃在当前石子堆的状态下的最优解，并存储在 s[i+1][int(math.Min(float64(len(piles)), float64(math.Max(float64(j), float64(m)))))] 中。

  • 循环结束后，将最优解保存到 f[index][m] 中，并返回最优解。

函数 second2 的作用是计算鲍勃在当前石子堆的状态下的最优解，与函数 second1 类似，但加入了记忆化搜索的机制。

  • 首先判断是否已经计算过该状态的结果，如果是，则直接返回存储的结果 s[index][m]。

  • 否则，继续计算最优解。

  • 在计算过程中，每一轮的最优解都会存储在 s[index][m]，以避免重复计算。

  • 循环结束后，将最优解保存到 s[index][m] 中，并返回最优解。

3.算法 stoneGameII3：严格位置依赖的动态规划，一张表的版本

  • 首先定义函数 stoneGameII3，接收一个石子堆的切片 piles 作为参数，并返回爱丽丝可以得到的最大数量的石头。

  • 在函数 stoneGameII3 中，首先初始化变量 n 为石子堆的数量，创建两个二维切片 f 和 s，表示爱丽丝和鲍勃在每个石子堆的状态下的最优解。

  • 利用循环，初始化 f 和 s 的值为 0。

  • 初始化变量 sum = 0，用于记录累计的石子数。

  • 从最后一个石子堆开始循环，更新变量 sum = sum + piles[index]，即计算当前的累计石子数。

  • 在循环中，根据动态规划的思想，计算爱丽丝和鲍勃的最优解。

  • 首先计算爱丽丝在当前石子堆状态下的最优解。

  • 声明变量 best = 0，表示当前的最优解。

  • 声明变量 pre = 0，表示当前已经取走的石子数量。

  • 在循环中，用变量 j 记录当前取走的石子堆的数量（初始值为 1）。

  • 在循环中，更新变量 pre = pre + piles[i]，即计算当前的已取走的石子数量。

  • 根据当前的石子堆状态以及剩余可取的石子堆的数量（int(math.Min(float64(len(piles)), float64(math.Max(float64(j), float64(m))))）），计算爱丽丝在下一轮的最优解 s[i+1][int(math.Min(float64(len(piles)), float64(math.Max(float64(j), float64(m)))))]。

  • 更新变量 best = int(math.Max(float64(best), float64(pre+s[i+1][int(math.Min(float64(len(piles)), float64(math.Max(float64(j), float64(m)))))])))，取当前轮最优解和已取走的石子数量之和的较大值作为当前的最优解。

  • 计算鲍勃在当前石子堆状态下的最优解。

  • 声明变量 worse = math.MaxInt64，表示当前的最差解。

  • 在循环中，用变量 j 记录当前取走的石子堆的数量（初始值为 1）。

  • 在循环中，更新变量 worse = int(math.Min(float64(worse), float64(f[i+1][int(math.Min(float64(len(piles)), float64(math.Max(float64(j), float64(m)))))])))，取当前轮最差解和已取走的石子数量之和的较小值作为当前的最差解。

  • 循环结束后，更新 f[index][m] = best 和 s[index][m] = worse。

  • 返回 f[0][1]，即爱丽丝在初始状态下的最优解。

4.算法 stoneGameII4：严格位置依赖的动态规划

  • 首先定义函数 stoneGameII4，接收一个石子堆的切片 piles 作为参数，并返回爱丽丝可以得到的最大数量的石头。

  • 在函数 stoneGameII4 中，首先初始化变量 n 为石子堆的数量，创建一个二维切片 dp，用于存储动态规划的结果。

  • 利用循环，初始化 dp 的值为 0。

  • 初始化变量 sum = 0，用于记录累计的石子数。

  • 从最后一个石子堆开始循环，更新变量 sum = sum + piles[i]，即计算当前的累计石子数。

  • 在循环中，根据动态规划的思想，计算爱丽丝的最优。

stoneGameII1的时间复杂度为$O(2^n)$，空间复杂度为$O(n)$。

stoneGameII2的时间复杂度为$O(n3)$，空间复杂度为$O(n2)$。

stoneGameII3的时间复杂度为$O(n3)$，空间复杂度为$O(n2)$。

stoneGameII4的时间复杂度为$O(n^2)$，空间复杂度为$O(n)$。

go完整代码如下：

package main

import (
	"fmt"
	"math"
)

// 暴力方法
func stoneGameII1(piles []int) int {
	return first1(piles, 0, 1)
}

func first1(piles []int, index, m int) int {
	if index == len(piles) {
		return 0
	}
	best := 0
	pre := 0
	for i, j := index, 1; i < len(piles) && j <= 2*m; i, j = i+1, j+1 {
		pre += piles[i]
		best = int(math.Max(float64(best), float64(pre+second1(piles, i+1, int(math.Max(float64(j), float64(m)))))))
	}
	return best
}

func second1(piles []int, index, m int) int {
	if index == len(piles) {
		return 0
	}
	worse := math.MaxInt64
	for i, j := index, 1; i < len(piles) && j <= 2*m; i, j = i+1, j+1 {
		worse = int(math.Min(float64(worse), float64(first1(piles, i+1, int(math.Max(float64(j), float64(m)))))))
	}
	return worse
}

// 记忆化搜索
func stoneGameII2(piles []int) int {
	n := len(piles)
	f := make([][]int, n)
	s := make([][]int, n)
	for i := 0; i < n; i++ {
		f[i] = make([]int, n+1)
		s[i] = make([]int, n+1)
		for j := 0; j <= n; j++ {
			f[i][j] = -1
			s[i][j] = -1
		}
	}
	return first2(piles, 0, 1, f, s)
}

func first2(piles []int, index, m int, f, s [][]int) int {
	if index == len(piles) {
		return 0
	}
	if f[index][m] != -1 {
		return f[index][m]
	}
	best := 0
	pre := 0
	for i, j := index, 1; i < len(piles) && j <= 2*m; i, j = i+1, j+1 {
		pre += piles[i]
		best = int(math.Max(float64(best), float64(pre+second2(piles, i+1, int(math.Min(float64(len(piles)), float64(math.Max(float64(j), float64(m))))), f, s))))
	}
	f[index][m] = best
	return best
}

func second2(piles []int, index, m int, f, s [][]int) int {
	if index == len(piles) {
		return 0
	}
	if s[index][m] != -1 {
		return s[index][m]
	}
	worse := math.MaxInt64
	for i, j := index, 1; i < len(piles) && j <= 2*m; i, j = i+1, j+1 {
		worse = int(math.Min(float64(worse), float64(first2(piles, i+1, int(math.Min(float64(len(piles)), float64(math.Max(float64(j), float64(m))))), f, s))))
	}
	s[index][m] = worse
	return worse
}

// 严格位置依赖的动态规划，一张表的版本
func stoneGameII3(piles []int) int {
	n := len(piles)
	f := make([][]int, n+1)
	s := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		f[i] = make([]int, n+1)
		s[i] = make([]int, n+1)
	}
	sum := 0
	for index := n - 1; index >= 0; index-- {
		sum += piles[index]
		for m := 1; m <= n; m++ {
			best := 0
			pre := 0
			for i, j := index, 1; i < len(piles) && j <= 2*m; i, j = i+1, j+1 {
				pre += piles[i]
				best = int(math.Max(float64(best), float64(pre+s[i+1][int(math.Min(float64(n), float64(math.Max(float64(j), float64(m)))))])))
			}
			f[index][m] = best
			worse := math.MaxInt64
			for i, j := index, 1; i < len(piles) && j <= 2*m; i, j = i+1, j+1 {
				worse = int(math.Min(float64(worse), float64(f[i+1][int(math.Min(float64(n), float64(math.Max(float64(j), float64(m)))))])))
			}
			s[index][m] = worse
		}
	}
	return f[0][1]
}

// 严格位置依赖的动态规划
func stoneGameII4(piles []int) int {
	n := len(piles)
	sum := 0
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := n - 1; i >= 0; i-- {
		sum += piles[i]
		for m := 1; m <= n; m++ {
			if i+2*m >= n {
				dp[i][m] = sum
			} else {
				nextMin := math.MaxInt64
				for x := 1; x <= 2*m; x++ {
					nextMin = int(math.Min(float64(nextMin), float64(dp[i+x][int(math.Max(float64(m), float64(x)))])))
				}
				dp[i][m] = sum - nextMin
			}
		}
	}
	return dp[0][1]
}

func main() {
	piles := []int{2, 7, 9, 4, 4}
	fmt.Println("stoneGameII1:", stoneGameII1(piles))
	fmt.Println("stoneGameII2:", stoneGameII2(piles))
	fmt.Println("stoneGameII3:", stoneGameII3(piles))
	fmt.Println("stoneGameII4:", stoneGameII4(piles))
}

在这里插入图片描述

rust完整代码如下：

fn stone_game_ii1(piles: Vec<i32>) -> i32 {
    first1(&piles, 0, 1)
}

fn first1(piles: &Vec<i32>, index: usize, m: i32) -> i32 {
    if index == piles.len() {
        return 0;
    }
    let mut best = 0;
    let mut pre = 0;
    for i in index..piles.len().min(index + (2 * m) as usize) {
        pre += piles[i];
        best = best.max(pre + second1(piles, i + 1, m.max(i as i32 + 1)));
    }
    best
}

fn second1(piles: &Vec<i32>, index: usize, m: i32) -> i32 {
    if index == piles.len() {
        return 0;
    }
    let mut worse = i32::MAX;
    for i in index..piles.len().min(index + (2 * m) as usize) {
        worse = worse.min(first1(piles, i + 1, m.max(i as i32 + 1)));
    }
    worse
}

fn stone_game_ii2(piles: Vec<i32>) -> i32 {
    let mut f = vec![vec![-1; piles.len() + 1]; piles.len()];
    let mut s = vec![vec![-1; piles.len() + 1]; piles.len()];

    first2(&piles, 0, 1, &mut f, &mut s)
}

fn first2(
    piles: &Vec<i32>,
    index: usize,
    m: usize,
    f: &mut Vec<Vec<i32>>,
    s: &mut Vec<Vec<i32>>,
) -> i32 {
    if index == piles.len() {
        return 0;
    }
    if f[index][m] != -1 {
        return f[index][m];
    }
    let mut best = 0;
    let mut pre = 0;
    for i in index..piles.len().min(index + 2 * m) {
        pre += piles[i];
        best = best.max(pre + second2(piles, i + 1, m.max(i - index + 1), f, s));
    }
    f[index][m] = best;
    best
}

fn second2(
    piles: &Vec<i32>,
    index: usize,
    m: usize,
    f: &mut Vec<Vec<i32>>,
    s: &mut Vec<Vec<i32>>,
) -> i32 {
    if index == piles.len() {
        return 0;
    }
    if s[index][m] != -1 {
        return s[index][m];
    }
    let mut worse = i32::MAX;
    for i in index..piles.len().min(index + 2 * m) {
        worse = worse.min(first2(piles, i + 1, m.max(i - index + 1), f, s));
    }
    s[index][m] = worse;
    worse
}

fn stone_game_ii3(piles: Vec<i32>) -> i32 {
    let n = piles.len();
    let mut f: Vec<Vec<i32>> = vec![vec![0; n + 1]; n + 1];
    let mut s: Vec<Vec<i32>> = vec![vec![0; n + 1]; n + 1];

    for index in (0..n).rev() {
        for m in 1..=n {
            let mut pre = 0;
            for (i, j) in (index..piles.len()).zip(1..=2 * m) {
                pre += piles[i];
                f[index][m] = f[index][m].max(pre + s[i + 1][n.min(j.max(m))]);
            }

            s[index][m] = i32::MAX;
            for (i, j) in (index..piles.len()).zip(1..=2 * m) {
                s[index][m] = s[index][m].min(f[i + 1][n.min(j.max(m))]);
            }
        }
    }

    f[0][1]
}

fn stone_game_ii4(piles: Vec<i32>) -> i32 {
    let n = piles.len();
    let mut sum = 0;
    let mut dp = vec![vec![0; n + 1]; n];

    for i in (0..n).rev() {
        sum += piles[i];
        for m in 1..=n {
            if i + 2 * m >= n {
                dp[i][m] = sum;
            } else {
                let mut next_min = std::i32::MAX;
                for x in 1..=2 * m {
                    next_min = next_min.min(dp[i + x][m.max(x)]);
                }
                dp[i][m] = sum - next_min;
            }
        }
    }

    dp[0][1]
}

fn main() {
    let piles = vec![2, 7, 9, 4, 4];
    let result = stone_game_ii1(piles);
    println!("{}", result);

    let piles = vec![2, 7, 9, 4, 4];
    let result = stone_game_ii2(piles);
    println!("{}", result);

    let piles = vec![2, 7, 9, 4, 4];
    let result = stone_game_ii3(piles);
    println!("{}", result);

    let piles = vec![2, 7, 9, 4, 4];
    let result = stone_game_ii4(piles);
    println!("{}", result);
}

在这里插入图片描述

c++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int second1(vector<int>& piles, int index, int m);

int first1(vector<int>& piles, int index, int m) {
    if (index == piles.size()) {
        return 0;
    }
    int best = 0;
    int pre = 0;
    for (int i = index, j = 1; i < piles.size() && j <= 2 * m; i++, j++) {
        pre += piles[i];
        best = max(best, pre + second1(piles, i + 1, max(j, m)));
    }
    return best;
}

int second1(vector<int>& piles, int index, int m) {
    if (index == piles.size()) {
        return 0;
    }
    int worse = INT_MAX;
    for (int i = index, j = 1; i < piles.size() && j <= 2 * m; i++, j++) {
        worse = min(worse, first1(piles, i + 1, max(j, m)));
    }
    return worse;
}

int stoneGameII1(vector<int>& piles) {
    return first1(piles, 0, 1);
}

int second2(vector<int>& piles, int index, int m, vector<vector<int>>& f, vector<vector<int>>& s);

int first2(vector<int>& piles, int index, int m, vector<vector<int>>& f, vector<vector<int>>& s) {
    if (index == piles.size()) {
        return 0;
    }
    if (f[index][m] != -1) {
        return f[index][m];
    }
    int best = 0;
    int pre = 0;
    for (int i = index, j = 1; i < piles.size() && j <= 2 * m; i++, j++) {
        pre += piles[i];
        best = max(best, pre + second2(piles, i + 1, min((int)piles.size(), max(j, m)), f, s));
    }
    f[index][m] = best;
    return best;
}

int second2(vector<int>& piles, int index, int m, vector<vector<int>>& f, vector<vector<int>>& s) {
    if (index == piles.size()) {
        return 0;
    }
    if (s[index][m] != -1) {
        return s[index][m];
    }
    int worse = INT_MAX;
    for (int i = index, j = 1; i < piles.size() && j <= 2 * m; i++, j++) {
        worse = min(worse, first2(piles, i + 1, min((int)piles.size(), max(j, m)), f, s));
    }
    s[index][m] = worse;
    return worse;
}

int stoneGameII2(vector<int>& piles) {
    int n = piles.size();
    vector<vector<int>> f(n, vector<int>(n + 1, -1));
    vector<vector<int>> s(n, vector<int>(n + 1, -1));
    return first2(piles, 0, 1, f, s);
}

int stoneGameII3(vector<int>& piles) {
    int n = piles.size();
    vector<vector<int>> f(n + 1, vector<int>(n + 1, 0));
    vector<vector<int>> s(n + 1, vector<int>(n + 1, 0));

    for (int index = n - 1; index >= 0; index--) {
        for (int m = 1; m <= n; m++) {
            int pre = 0;
            for (int i = index, j = 1; i < n && j <= 2 * m; i++, j++) {
                pre += piles[i];
                f[index][m] = max(f[index][m], pre + s[i + 1][min(n, max(j, m))]);
            }
            s[index][m] = INT_MAX;
            for (int i = index, j = 1; i < n && j <= 2 * m; i++, j++) {
                s[index][m] = min(s[index][m], f[i + 1][min(n, max(j, m))]);
            }
        }
    }
    return f[0][1];
}

int stoneGameII4(vector<int>& piles) {
    int n = piles.size();
    int sum = 0;
    vector<vector<int>> dp(n, vector<int>(n + 1, 0));
    for (int i = n - 1; i >= 0; i--) {
        sum += piles[i];
        for (int m = 1; m <= n; m++) {
            if (i + 2 * m >= n) {
                dp[i][m] = sum;
            }
            else {
                int nextMin = INT_MAX;
                for (int x = 1; x <= 2 * m; x++) {
                    nextMin = min(nextMin, dp[i + x][max(m, x)]);
                }
                dp[i][m] = sum - nextMin;
            }
        }
    }
    return dp[0][1];
}

int main() {
    vector<int> piles = { 2, 7, 9, 4, 4 };
    cout << "stoneGameII1: " << stoneGameII1(piles) << endl;
    cout << "stoneGameII2: " << stoneGameII2(piles) << endl;
    cout << "stoneGameII3: " << stoneGameII3(piles) << endl;
    cout << "stoneGameII4: " << stoneGameII4(piles) << endl;
    return 0;
}

在这里插入图片描述

c完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int second1(int* piles, int pilesSize, int index, int m);

int first1(int* piles, int pilesSize, int index, int m) {
    if (index == pilesSize) {
        return 0;
    }
    int best = 0;
    int pre = 0;
    for (int i = index, j = 1; i < pilesSize && j <= 2 * m; i++, j++) {
        pre += piles[i];
        best = best > (pre + second1(piles, pilesSize, i + 1, j > m ? j : m)) ? best : (pre + second1(piles, pilesSize, i + 1, j > m ? j : m));
    }
    return best;
}

int second1(int* piles, int pilesSize, int index, int m) {
    if (index == pilesSize) {
        return 0;
    }
    int worse = INT_MAX;
    for (int i = index, j = 1; i < pilesSize && j <= 2 * m; i++, j++) {
        worse = worse < first1(piles, pilesSize, i + 1, j > m ? j : m) ? worse : first1(piles, pilesSize, i + 1, j > m ? j : m);
    }
    return worse;
}

int stoneGameII1(int* piles, int pilesSize) {
    return first1(piles, pilesSize, 0, 1);
}

int second2(int* piles, int pilesSize, int index, int m, int** f, int** s);

int first2(int* piles, int pilesSize, int index, int m, int** f, int** s) {
    if (index == pilesSize) {
        return 0;
    }
    if (f[index][m] != -1) {
        return f[index][m];
    }
    int best = 0;
    int pre = 0;
    for (int i = index, j = 1; i < pilesSize && j <= 2 * m; i++, j++) {
        pre += piles[i];
        best = best > (pre + second2(piles, pilesSize, i + 1, j > m ? j : m, f, s)) ? best : (pre + second2(piles, pilesSize, i + 1, j > m ? j : m, f, s));
    }
    f[index][m] = best;
    return best;
}

int second2(int* piles, int pilesSize, int index, int m, int** f, int** s) {
    if (index == pilesSize) {
        return 0;
    }
    if (s[index][m] != -1) {
        return s[index][m];
    }
    int worse = INT_MAX;
    for (int i = index, j = 1; i < pilesSize && j <= 2 * m; i++, j++) {
        worse = worse < first2(piles, pilesSize, i + 1, j > m ? j : m, f, s) ? worse : first2(piles, pilesSize, i + 1, j > m ? j : m, f, s);
    }
    s[index][m] = worse;
    return worse;
}

int stoneGameII2(int* piles, int pilesSize) {
    int n = pilesSize;
    int** f = (int**)malloc((n + 1) * sizeof(int*));
    int** s = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i < n; i++) {
        f[i] = (int*)malloc((n + 1) * sizeof(int));
        s[i] = (int*)malloc((n + 1) * sizeof(int));
        for (int j = 0; j <= n; j++) {
            f[i][j] = -1;
            s[i][j] = -1;
        }
    }
    return first2(piles, pilesSize, 0, 1, f, s);
}

int stoneGameII3(int* piles, int pilesSize) {
    int n = pilesSize;
    int** f = (int**)malloc((n + 1) * sizeof(int*));
    int** s = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        f[i] = (int*)malloc((n + 1) * sizeof(int));
        s[i] = (int*)malloc((n + 1) * sizeof(int));
        for (int j = 0; j <= n; j++) {
            f[i][j] = 0;
            s[i][j] = 0;
        }
    }

    for (int index = n - 1; index >= 0; index--) {
        for (int m = 1; m <= n; m++) {
            int pre = 0;
            for (int i = index, j = 1; i < n && j <= 2 * m; i++, j++) {
                pre += piles[i];
                f[index][m] = f[index][m] > (pre + s[i + 1][j > m ? j : m]) ? f[index][m] : (pre + s[i + 1][j > m ? j : m]);
            }
            s[index][m] = INT_MAX;
            for (int i = index, j = 1; i < n && j <= 2 * m; i++, j++) {
                s[index][m] = s[index][m] < f[i + 1][j > m ? j : m] ? s[index][m] : f[i + 1][j > m ? j : m];
            }
        }
    }
    return f[0][1];
}

int stoneGameII4(int* piles, int pilesSize) {
    int n = pilesSize;
    int sum = 0;
    int** dp = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        dp[i] = (int*)malloc((n + 1) * sizeof(int));
        for (int j = 0; j <= n; j++) {
            dp[i][j] = 0;
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        sum += piles[i];
        for (int m = 1; m <= n; m++) {
            if (i + 2 * m >= n) {
                dp[i][m] = sum;
            }
            else {
                int nextMin = INT_MAX;
                for (int x = 1; x <= 2 * m; x++) {
                    nextMin = nextMin < dp[i + x][m > x ? m : x] ? nextMin : dp[i + x][m > x ? m : x];
                }
                dp[i][m] = sum - nextMin;
            }
        }
    }
    return dp[0][1];
}

int main() {
    int piles[] = { 2, 7, 9, 4, 4 };
    int pilesSize = sizeof(piles) / sizeof(piles[0]);
    printf("stoneGameII1: %d\n", stoneGameII1(piles, pilesSize));
    printf("stoneGameII2: %d\n", stoneGameII2(piles, pilesSize));
    printf("stoneGameII3: %d\n", stoneGameII3(piles, pilesSize));
    printf("stoneGameII4: %d\n", stoneGameII4(piles, pilesSize));
    return 0;
}

在这里插入图片描述

标签：index,鲍勃,piles,float64,int,石子,pilesSize,爱丽丝
From： https://www.cnblogs.com/moonfdd/p/17529938.html

相关文章

  • 1140.石子游戏 II
    问题描述1140.石子游戏II(Medium)爱丽丝和鲍勃继续他们的石子游戏。许多堆石子排成一行，每堆都有正整数颗石子piles[i]。游戏以谁手中的石子最多来决出胜负。爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，M=1。在每个玩家的回合中，该玩家可以拿走剩下的前X堆的所有石子，其......
  • 石子合并（弱化版）
    石子合并（弱化版）题目描述设有\(N(N\le300)\)堆石子排成一排，其编号为\(1,2,3,\cdots,N\)。每堆石子有一定的质量\(m_i(m_i\le1000)\)。现在要将这\(N\)堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新......
  • 区间PD之石子合并
    设有 N堆石子排成一排，其编号为 1,2,3,…,N每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。例如有......
  • luogu P8497 [NOI2022] 移除石子
    题面传送门不好评价？首先我们考虑最基础的情况，当\(k=0,l_i=r_i\)时，相当于我们需要判定一个状态能不能被消完。这相当于我们要执行若干次\(2\)操作，使得每个位置要么大于等于\(2\)，要么为\(0\)。为此我们需要挖掘一些操作\(2\)的性质。性质\(1\)：操作区间长度不会超过\(5......
  • 石子合并问题
    石子合并问题是最经典的DP问题。首先它有如下3种题型：(1)有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动任意的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费最小（或最大）。分析：当然这种情况是最简单的情况，合并的是任意两堆，直接贪心即可，......
  • 取石子游戏与SG函数
    题目:http://acm.hdu.edu.cn/showproblem.php?pid=1848题意:有3堆石子,石子数量分别为a,b,c,有两个玩家,每次只能从任意一堆中取f个,这里的f只能为fibnacci数,问是先手胜还是先手败.分析:由于石子的数量都在1000以内,那么我们可以先预处理出1000以内的SG函数值,然后对于3堆石子,我......
  • 石子合并(GarsiaWachs算法)
    对于石子合并问题，有一个最好的算法，那就是GarsiaWachs算法。时间复杂度为O(n^2)。它的步骤如下：设序列是stone[]，从左往右，找一个满足stone[k-1]<= stone[k+1]的k，找到后合并stone[k]和stone[k-1]，再从当前位置开始向左找最大的j，使其满足stone[j]> stone[k]+stone[k-1]，插到j的后面就......
  • 1218：取石子游戏
     #include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;booljs(inta,intb){if(a<b)swap(a,b);if(a%b==0)returntrue;for(intk=a/b;k>=1;k--)if(!js((a-b*k),b))returntrue;ret......
  • 2023-05-09：石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。 有 n 块石子排
    2023-05-09：石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始。有n块石子排成一排。每个玩家的回合中，可以从行中移除最左边的石头或最右边的石头，并获得与该行中剩余石头值之和相等的得分。当没有石头可移除时，得分较高者获胜。鲍勃发现他总是输掉游戏（可怜的鲍勃，他......
  • 1033. 移动石子直到连续
    1033.移动石子直到连续三枚石子放置在数轴上，位置分别为a，b，c。每一回合，你可以从两端之一拿起一枚石子（位置最大或最小），并将其放入两端之间的任一空闲位置。形式上，假设这三枚石子当前分别位于位置x,y,z且x<y<z。那么就可以从位置x或者是位置z拿起一枚石子，并将该石......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99