本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
AcWing：4920. 乘法谜题 - AcWing题库
【题目描述】
乘法谜题是一个益智游戏，规则如下：
- 给定一个长度为n nn的正整数序列。
- 在每轮操作中，你需要选择当前序列中的一个现存元素（不能选第一个元素和最后一个元素）并将其从序列中消除。在消除该元素前，其左右两侧一定都存在相邻元素（相邻元素指现存元素中与其相邻的元素），将这三个元素相乘得到的乘积就是你此轮操作的得分。
- 当序列长度不足3 33时，游戏结束。
我们的目标是最小化所有操作的总得分。
例如，给定序列10 , 1 , 50 , 20 , 5 10,1,50,20,510,1,50,20,5，如果我们依次选择消除1 , 20 , 50 1,20,501,20,50，则总得分为10 × 1 × 50 + 50 × 20 × 5 + 10 × 50 × 5 = 500 + 5000 + 2500 = 8000 10×1×50+50×20×5+10×50×5=500+5000+2500=800010×1×50+50×20×5+10×50×5=500+5000+2500=8000，如果我们依次选择消除50 , 20 , 1 50,20,150,20,1，则总得分为1 × 50 × 20 + 1 × 20 × 5 + 10 × 1 × 5 = 1000 + 100 + 50 = 1150 1×50×20+1×20×5+10×1×5=1000+100+50=11501×50×20+1×20×5+10×1×5=1000+100+50=1150。
【输入】
第一行包含整数N NN。
第二行包含N NN个整数，表示给定正整数序列。
【输出】
一个整数，表示总得分的最小可能值。
【输入样例】
6 10 1 50 50 20 5【输出样例】
3650【解题思路】
![[Pasted image 20260612100331.png|782]]
![[Pasted image 20260612100819.png|784]]
【算法标签】
#区间DP
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;// 定义数组最大容量constintN=105;// 全局变量声明intn;// 顶点数量inta[N];// 存储各顶点的权值intf[N][N];// 动态规划数组，f[i][j]表示从顶点i到顶点j的最优三角剖分代价// 主函数入口intmain(){// 读取顶点数量cin>>n;// 读取各顶点的权值for(inti=1;i<=n;i++)cin>>a[i];// 区间DP：枚举区间长度for(intlen=3;len<=n;len++){// 枚举区间左端点for(inti=1;i+len-1<=n;i++){intj=i+len-1;// 区间右端点f[i][j]=0x3f3f3f3f;// 初始化为无穷大// 枚举中间顶点k，将多边形划分为两个子多边形和一个三角形for(intk=i+1;k<j;k++)f[i][j]=min(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]);}}// 输出整个多边形的最优三角剖分代价cout<<f[1][n]<<endl;return0;}【运行结果】
6 10 1 50 50 20 5 3650
)
