牛客春招刷题训练营-2025.4.29题解

活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 游游的数字圈

• 使用 fmt.Scan() 读取输入字符串
• 用 for range 遍历字符串中的每个字符
• 通过 switch 语句判断字符：
  • 如果是 '0'、'6' 或 '9'，圆圈数 +1
  • 如果是 '8'，圆圈数 +2
  • 其他字符不处理
• 最后输出总圆圈数

package main

import "fmt"

func main() {
	var t int
	fmt.Scan(&t)
	for i := 0; i < t; i++ {
		var x int
		fmt.Scan(&x)
		if x%2 == 0 {
			fmt.Println("YES")
		} else {
			fmt.Println("NO")
		}
	}
}

中等题 最小花费爬楼梯

1. 输入处理：

   • 读取数组长度 n
   • 读取 n 个整数，表示每个台阶的代价

2. 动态规划解法：

   • 创建 dp 数组，长度为 n+1
   • dp[i] 表示到达第 i 个位置的最小花费
   • 状态转移方程：
     • dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
     • 表示可以从前一个台阶或前两个台阶跳过来，取最小值

3. 具体实现：

   • dp[0] 和 dp[1] 默认为 0（起始点）
   • 从 i=2 开始遍历到 n
   • 每次取前一步和前两步的最小值
   • 最终 dp[n] 就是答案

package main

import "fmt"

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}
	dp := make([]int, n+1)
	for i := 2; i <= n; i++ {
		dp[i] = min(dp[i-1]+a[i-1], dp[i-2]+a[i-2])
	}
	fmt.Println(dp[n])
}

困难题 取数游戏

1. 问题分析：

• 给定两个长度为 n 的数组 a 和 b
• 每次可以从 a 的两端取一个数，与 b 数组按顺序相乘
• 求所有取数方案中，乘积之和的最大值

2. DP状态设计：

• dp[l][r] 表示从 a 数组左边取了 l 个数，右边取了 r 个数时的最大乘积和
• l + r 表示当前已经取了多少个数
• b 数组是按顺序使用的，当前使用的是 b[l+r]

3. 状态转移：

• 对于每个位置 i (表示已取数的总数)，枚举左边取了多少个数 l
• 右边取的数就是 r = i - l
• 有两种转移方式：
  1. 从左边取：dp[l][r] = dp[l-1][r] + a[l]*b[i]
  2. 从右边取：dp[l][r] = dp[l][r-1] + a[n-r+1]*b[i]
• 取这两种方式的最大值

4. 边界条件：

• 当 l = 0 时，只能从右边取数
• 当 r = 0 时，只能从左边取数

5. 最终答案：

• 遍历所有满足 l + r = n 的情况，取最大值

package main

import "fmt"

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n+1)
	for i := 1; i <= n; i++ {
		fmt.Scan(&a[i])
	}
	b := make([]int, n+1)
	for i := 1; i <= n; i++ {
		fmt.Scan(&b[i])
	}
	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, n+1)
	}

	for i := 1; i <= n; i++ {
		for l := 0; l <= i; l++ {
			r := i - l
			if l == 0 {
				dp[l][r] = dp[l][r-1] + a[n-r+1]*b[i]
			} else if r == 0 {
				dp[l][r] = dp[l-1][r] + a[l]*b[i]
			} else {
				dp[l][r] = max(dp[l-1][r]+a[l]*b[i], dp[l][r-1]+a[n-r+1]*b[i])
			}
		}
	}

	ans := 0
	for l := 0; l <= n; l++ {
		r := n - l
		ans = max(ans, dp[l][r])
	}
	fmt.Println(ans)
}