欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年白银组真题解析 | 汇总-CSDN博客
P3004 Treasure Chest
【题目来源】
洛谷：[P3004 USACO10DEC] Treasure Chest S - 洛谷
【题目描述】
Bessie 和 Bonnie 发现了一个装满了非凡的金币的宝箱!作为奶牛，尽管，他们无法走进一家商店购买物品，因此他们决定开心的玩一玩这些金币。\(N(1\le N\le 5000)\) 个金币放置在一条直线上，每个金币的价值为\(C_i(1\le C_i\le 5000)\)。Bessie 和Bonnie轮流操作，每一轮中，她从直线的左端或者右端取走一枚金币。金币全部取完时游戏结束。
Bessie 和 Bonnie 都想要让自己尽可能得到更多的财富。Bessie 先开始游戏。请帮忙她算出她能获得的最大价值。假设两个奶牛都以最优的方法进行游戏。
考虑一局游戏，四个金币排成一行，价值如下所示：30 25 10 35
考虑如下的游戏过程：
这是Bessie 能做到的最优游戏方式。
【输入】
行\(1\)：一个数\(N\)。行\(2..N+1\)：行\(i+1\)为一个整数\(C_i\)
【输出】
行\(1\)：一个整数，即Bessie 能赢得的最大价值。
【输入样例】
4
30
25
10
35
【输出样例】
60
【算法标签】
《洛谷 P3004 宝箱》 #动态规划,dp# #递推# #USACO# #2010#
【代码详解】
//该代码会有一个MLE
// 引入所有标准库头文件，方便使用各种标准库功能
#include <bits/stdc++.h>// 使用标准命名空间，避免每次使用标准库函数时都需要加 std:: 前缀
using namespace std;// 定义常量
const int N = 5005; // 定义金币数量的最大值为5005// 定义全局变量
int f[N][N]; // f[i][j]: 表示在区间(i, j)内先拿金币时，能取得的最大价值
int n, c[N]; // n: 金币的总数量，c[N]: 存储每个金币的价值，c[i]表示第i个金币的价值
int s[N]; // s[N]: 前缀和数组，s[i]表示前i个金币的总价值// 主函数，程序的入口点
int main()
{// 读取金币的总数量 ncin >> n; // N金币数量// 循环读取每个金币的价值，并计算前缀和数组 s[j]for (int j = 1; j <= n; j++) {// 读取第j个金币的价值cin >> c[j]; // 读入金币价值// 计算前缀和：s[j] = s[j-1] + 当前金币的价值s[j] = s[j - 1] + c[j]; // s[i]前缀和，前i金币价值和}// =============================// 边界条件初始化// =============================// 对于区间长度为1的情况，即只有一个金币，先拿的最大价值就是该金币的价值for (int i = 1; i <= n; i++) {f[i][i] = c[i]; // 边界：区间长度1，只有一个金币，先拿最大值是金币值}// =============================// 动态规划部分：计算在区间(i, j)内先拿金币时能取得的最大价值// =============================// 外层循环：遍历所有可能的区间长度 len，从2到nfor (int len = 2; len <= n; len++) {// 中层循环：遍历所有可能的起始位置 i，确保区间(i, j)在有效范围内for (int i = 1; i <= n - len + 1; i++) {// 计算区间的结束位置 jint j = i + len - 1;// 更新在区间(i, j)内先拿金币时能取得的最大价值// f[i][j] = s[j] - s[i-1] - min(f[i+1][j], f[i][j-1])// 解释：// s[j] - s[i-1] 表示区间(i, j)内所有金币的总价值// min(f[i+1][j], f[i][j-1]) 表示对手在剩下的区间内能取得的最大价值（取最小值，因为对手会采取最优策略）// 因此，f[i][j] 表示当前玩家在区间(i, j)内先拿金币时，能取得的最大价值f[i][j] = s[j] - s[i - 1] - min(f[i + 1][j], f[i][j - 1]);}}// =============================// 输出结果：在整个区间(1, n)内先拿金币时能取得的最大价值// =============================// 输出 f[1][n]，即在整个金币序列中先拿金币时能取得的最大价值cout << f[1][n] << endl;// 程序正常结束，返回 0return 0;
}
// 引入所有标准库头文件，方便使用各种标准库功能
#include <bits/stdc++.h>// 使用标准命名空间，避免每次使用标准库函数时都需要加 std:: 前缀
using namespace std;// 定义常量
const int N = 5005; // 定义金币数量的最大值为5005// 定义全局变量
int f[N]; // f[i]: 表示在区间(i, j)内先拿金币时，能取得的最大价值（当前实现可能有误，应为区间[i, j]）
int n, c[N]; // n: 金币的总数量，c[N]: 存储每个金币的价值，c[i]表示第i个金币的价值
int s[N]; // s[N]: 前缀和数组，s[i]表示前i个金币的总价值// 主函数，程序的入口点
int main()
{// 读取金币的总数量 ncin >> n; // N金币数量// 循环读取每个金币的价值，并计算前缀和数组 s[j]for (int j = 1; j <= n; j++) {// 读取第j个金币的价值cin >> c[j]; // 读入金币价值// 计算前缀和：s[j] = s[j-1] + 当前金币的价值s[j] = s[j - 1] + c[j]; // s[i]前缀和，前i金币价值和}// =============================// 边界条件初始化// =============================// 对于区间长度为1的情况，即只有一个金币，先拿的最大价值就是该金币的价值for (int i = 1; i <= n; i++) {f[i] = c[i]; // 边界：区间长度1，只有一个金币，先拿最大值是金币值}// =============================// 动态规划部分：计算在区间(i, j)内先拿金币时能取得的最大价值// =============================// 外层循环：遍历所有可能的区间长度 len，从2到nfor (int len = 2; len <= n; len++) {// 中层循环：遍历所有可能的起始位置 i，确保区间(i, j)在有效范围内for (int i = 1; i <= n - len + 1; i++) {// 计算区间的结束位置 jint j = i + len - 1;// 更新在区间(i, j)内先拿金币时能取得的最大价值// f[i] = s[j] - s[i-1] - min(f[i+1], f[i])// 解释：// s[j] - s[i-1] 表示区间(i, j)内所有金币的总价值// min(f[i+1], f[i]) 表示对手在剩下的区间内能取得的最大价值（取最小值，因为对手会采取最优策略）// 因此，f[i] 表示当前玩家在区间(i, j)内先拿金币时，能取得的最大价值f[i] = s[j] - s[i - 1] - min(f[i + 1], f[i]);}}// =============================// 输出结果：在整个区间(1, n)内先拿金币时能取得的最大价值// =============================// 输出 f[1]，即在整个金币序列中先拿金币时能取得的最大价值cout << f[1] << endl;// 程序正常结束，返回 0return 0;
}
【运行结果】
4
30
25
10
35
60