2026年noip算法题中动态规划的深入解读

2026年noip算法题中动态规划的深入解读第一部分：背包问题（3题，共45分）1.（15分）多物品背包问题——电子购物问题描述：某电商平台推出“满减”活动，顾客需从n种商品中选择若干件购买，每种商品有无限件可选。每件商品i的重量为Wi，价值为Vi。为了促销，顾客购买总重量恰好为W的商品时，可享受额外价值Di的折扣。请计算顾客能获得的最大总价值。输入格式：第一行输入两个整数n和W（1≤n≤200，1≤W≤2000）。接下来n行，每行输入三个整数Wi，Vi，Di（1≤Wi≤200，1≤Vi≤1000，0≤Di≤500）。输出格式：输出一个整数，表示最大总价值。示例：输入：310241352460输出：12解析：选择两件重量为4的商品（价值6），再选择一件重量为2的商品（价值4+1折扣），总价值为12。2.（15分）多重背包问题——资源分配问题描述：某公司有m种资源，每种资源i的总量为Ci，每单位资源可带来价值Pi。公司需要分配资源给n个项目，每个项目j需要资源量Ai，且项目j的收益为Bj。若项目j使用的资源总量超过其需求，则收益会因效率损失减少。请计算公司能获得的最大总收益。输入格式：第一行输入n和m（1≤n≤150，1≤m≤30）。接下来n行，每行输入三个整数Ai和Bj（1≤Ai≤1000，1≤Bj≤10000）。接下来m行，每行输入Ci和Pi（1≤Ci≤1000，1≤Pi≤100）。输出格式：输出一个整数，表示最大总收益。示例：输入：223104155837输出：27解析：项目1使用3单位资源（收益10），项目2使用1单位资源（收益15-2损失=13），总收益27。3.（15分）完全背包问题——任务分配问题描述：某团队有n项任务，任务i的执行时间为Ti，收益为Si。团队有m台机器，每台机器初始状态为空闲。若同一时间只能执行一项任务，但任务可重复分配。请计算团队能获得的最大总收益。输入格式：第一行输入n和m（1≤n≤200，1≤m≤50）。接下来n行，每行输入Ti和Si（1≤Ti≤20，1≤Si≤200）。接下来一行输入m个整数，表示每台机器的剩余可用时间（1≤每个整数≤200）。输出格式：输出一个整数，表示最大总收益。示例：输入：3221031542053输出：35解析：一台机器执行任务1（收益10），另一台机器执行任务2和任务3（收益15+20-5损失=30），总收益35。第二部分：区间动态规划（2题，共35分）4.（15分）区间最值问题——生命游戏问题描述：在一个m×n的网格中，每个格子初始状态为“活”或“死”。每一步，格子的状态由其相邻八格（上下左右和对角线）的活细胞数量决定：若活细胞数量为2或3，该格子保持“活”；否则变为“死”。请计算经过k步后，网格中最大连续“活”格子数量。输入格式：第一行输入m，n，k（1≤m≤100，1≤n≤100，1≤k≤100）。接下来m行，每行输入n个字符（'0'表示“死”，'1'表示“活”）。输出格式：输出一个整数，表示最大连续“活”格子数量。示例：输入：341101001011010输出：4解析：经过1步后，全网格变为“活”，最大连续“活”格子数量为4。5.（20分）区间最长序列问题——课程选择问题描述：某校开设n门课程，课程i与课程j冲突当且仅当i与j的集合交集非空。学生需选择不冲突的子集，且子集中课程按编号严格递增。请计算学生能选择的最长课程序列长度。输入格式：第一行输入n（1≤n≤200）。接下来n行，每行输入一个集合Si，表示课程i的冲突课程集合（用空格分隔）。输出格式：输出一个整数，表示最长序列长度。示例：输入：423131214输出：3解析：选择课程1、3、4（不冲突），最长序列长度为3。第三部分：树形动态规划（2题，共30分）6.（15分）树上最值路径问题——网络传输问题描述：给定一棵树，节点代表网络设备，边代表传输链路。每个链路i的传输能力为Wi。若从节点1到节点k的路径上所有链路传输能力之积不超过C，则该路径有效。请计算最多有多少条有效路径。输入格式：第一行输入n和C（1≤n≤200，1≤C≤10^9）。接下来n-1行，每行输入三个整数ui，vi，Wi（1≤ui,vi≤n，1≤Wi≤10^9），表示树边。输出格式：输出一个整数，表示最多有效路径数。示例：输入：5100121013202452510输出：3解析：有效路径有1-2-4、1-2-5、1-3，共3条。7.（15分）树上区间和问题——信号覆盖问题描述：给定一棵树，节点代表基站，边代表信号覆盖范围。每个节点i的信号强度为Si。若节点j与节点i的路径长度不超过d，则j可被i覆盖。请计算最多有多少节点可被任意节点覆盖。输入格式：第一行输入n和d（1≤n≤150，1≤d≤50）。接下来n-1行，每行输入三个整数ui，vi，Wi（1≤ui,vi≤n，1≤Wi≤100），表示树边。接下来一行输入n个整数Si（1≤Si≤100）。输出格式：输出一个整数，表示最多可覆盖节点数。示例：输入：4212113234110203040输出：3解析：节点1覆盖节点2、节点3，节点3覆盖节点4，最多覆盖3个节点。答案与解析第一部分：背包问题1.多物品背包问题思路：按重量排序商品，用动态规划dp[w]表示重量为w时的最大价值。对于每件商品，考虑其额外折扣后的价值，更新dp数组。代码伪代码：pythonsortitemsbyWiascendingforeachitem:forwinWdowntoWi:dp[w]=max(dp[w],dp[w-Wi]+Vi-Diifw>=WielseVi)printdp[W]2.多重背包问题思路：容量转化为完全背包。将每种资源拆分为若干重量为Ci的小背包，再用完全背包处理。代码伪代码：pythonforeachresource:forkin1toCi//m:additem(kWi,kPi)solveascompleteknapsack3.完全背包问题思路：直接用完全背包处理，按时间排序任务，更新dp数组。代码伪代码：pythonsorttasksbyTiascendingforeachtask:forwinmdowntoTi:dp[w]=max(dp[w],dp[w-Ti]+Si)printsummax(dp[w]forwinmachinelimits)第二部分：区间动态规划4.区间最值问题思路：使用二维动态规划，dp[i][j]表示区间[i,j]的最大连续“活”格子数。枚举分割点，合并左右区间结果。代码伪代码：pythonforstepin1tok:foriin1tom:forjinitomin(i+n-1,m):count=sumgrid[i-l][j-l]forvalidldp[i][j]=max(dp[i][j],count)printmaxdp[i][j]5.区间最长序列问题思路：按课程编号排序，使用动态规划dp[i]表示以i结尾的最长序列长度。枚举前驱冲突关系。代码伪代码：pythonsortcoursesbyiddp[0]=1foriin1ton:dp[i]=1forjin0toi-1:ifnoconflictbetweeniandj:dp[i]=max(dp[i],dp[j]+1)printmaxdp[i]第三部分：树形动态规划6.树上最值路径问题思路：DFS遍历树，记录路径乘积，统计满足条件的路径数。代码伪代码：pythondfs(u,parent=0):product=1count=0forvinchildren[u]:ifv!=parent:child_product=dfs(v,u)ifproductchild_product<=C:count+=child_productproduct=child_productreturncountprintdfs(1)7.树上区间和问题思路：DFS遍历树，使用动态规划记录以每