本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing4920. 乘法谜题 - 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×5050×20×510×50×550050002500800010×1×5050×20×510×50×5500500025008000如果我们依次选择消除50 , 20 , 1 50,20,150,20,1则总得分为1 × 50 × 20 1 × 20 × 5 10 × 1 × 5 1000 100 50 1150 1×50×201×20×510×1×510001005011501×50×201×20×510×1×51000100501150。【输入】第一行包含整数N NN。第二行包含N NN个整数表示给定正整数序列。【输出】一个整数表示总得分的最小可能值。【输入样例】6 10 1 50 50 20 5【输出样例】3650【解题思路】![[Pasted image 20260612100331.png|782]]![[Pasted image 20260612100819.png|784]]【算法标签】#区间DP【代码详解】#includebits/stdc.husingnamespacestd;// 定义数组最大容量constintN105;// 全局变量声明intn;// 顶点数量inta[N];// 存储各顶点的权值intf[N][N];// 动态规划数组f[i][j]表示从顶点i到顶点j的最优三角剖分代价// 主函数入口intmain(){// 读取顶点数量cinn;// 读取各顶点的权值for(inti1;in;i)cina[i];// 区间DP枚举区间长度for(intlen3;lenn;len){// 枚举区间左端点for(inti1;ilen-1n;i){intjilen-1;// 区间右端点f[i][j]0x3f3f3f3f;// 初始化为无穷大// 枚举中间顶点k将多边形划分为两个子多边形和一个三角形for(intki1;kj;k)f[i][j]min(f[i][j],f[i][k]f[k][j]a[i]*a[k]*a[j]);}}// 输出整个多边形的最优三角剖分代价coutf[1][n]endl;return0;}【运行结果】6 10 1 50 50 20 5 3650