搜狗历年秋招笔试真题

如需获取完整资料，请点击下方链接领取《2024校招笔试真题秘籍》（实时更新中）

不收费，3人组团即可一块免费领取！限量免费10000个名额

手机端点击免费领取：https://www.nowcoder.com/link/campus_xzbs2

电脑端请扫码领取：

1、糖果

【题目描述】小明和小红都很喜欢吃糖果，今天他们一起玩一个糖果游戏。他们将装有不同数量的透明糖果盒子摆放成一个环，现在两人依次选择糖果盒子，小明先拿，且小明第一次挑选可以选择环中任意一个糖果盒子，将环分割成一列有首尾的序列，之后两人每次选择时只能从剩余的糖果盒子序列的行首或者行尾挑选，直到两人将糖果盒子全部拿完，最后糖果多的为胜者。假设两人都希望自己是最后的赢家，且糖果的总数是奇数，现给定一个糖果的环，用一个数组表示环中的各糖果盒子中糖果的数量，数组首尾相连成环，元素个数为N。请输出胜利者比失败者至少多拿多少糖果。

输入描述:

第一行：N

第2至N+1行：每行一个数，代表糖果数

输出描述:

一个数，请输出胜利者比失败者多拿多少糖果

输入样例:

4

1

55

41

2

输出样例:

54

小明先选择55，此时环从55处断开，变为序列[41, 2, 1]

小红选择行首的41，此时剩余的序列为[2, 1]

小明选择行首的2，此时剩余的序列为[1]

小红选择剩余的1。

此时小明胜利，比小红多15个糖果

【解题思路】

带博弈的动态规划。

设dp[i][j]为只考虑i~j的糖果序列，先手能比后手多的糖果数，则转移方程为

dp[i][j] = max(a[i] - dp[i+1][j], a[j] - dp[i][j-1])

为环的话，只需要枚举第一个取的糖果，即可转为序列上的问题。

【参考代码】

#include <iostream>
#include <vector>
using namespace std;

int predictWinner(vector<int> candies) {
	int length = candies.size();
	if (length == 0) return false;
	vector<vector<int> > dp(length, vector<int>(length, 0));
	for (int i = 0; i < length; i++) {
		dp[i][i] = candies