oj题完全背包-北京尧图网络

题意分析我们定义dp[x]拼成总长度为x的棒能得到的最大武力值。规则基础情况直接用一根短棒a_i如果a_i x那么dp[x]可以取b_i。合并规则把两根棒长度 A、B拼接成长度AB的棒若A ! Bdp[AB] max(dp[AB], dp[A] dp[B])若A B Kdp[2K] max(dp[2K], dp[K] * 2 233)短棒无限数量目标求dp[M]。算法思路初始化 dp 数组dp大小为M1初始值设为负无穷。预处理对于每一种短棒(a_i,b_i)如果a_i M更新dp[a_i] max(dp[a_i], b_i)。从小到大枚举长度len从 1~M枚举 A 从1 ~ len/2B len - A如果dp[A]和dp[B]不是负无穷代表 A、B 都可以拼出来如果A Bdp[len] max(dp[len], dp[A]*2 233)如果A ! Bdp[len] max(dp[len], dp[A]dp[B])最后输出dp[M]为什么从小到大遍历因为要拼出长度 len需要的 A,B 一定比 len 小已经提前算好 dp [A], dp [B]。c代码#includebits/stdc.h using namespace std; const int N1e310,M1e3,V233,INF1e8; int n,m,a[N],b[N],dp[N]; int main(){ scanf(%d%d,n,m); for(int i1;iM;i)dp[i]-INF; for(int i1;in;i){ scanf(%d,a[i]); } for(int i1;in;i){ scanf(%d,b[i]); for(int ja[i];jM;j){ dp[j]max(dp[j],dp[j-a[i]]b[i]); } } for(int i2;iM;i){ dp[i]max(dp[i],dp[i/2]*2V); for(int j1;ji;j){ dp[i]max(dp[i],dp[j]dp[i-j]); } } printf(%d\n,dp[m]); return 0; }

oj题完全背包

相关推荐

SyncToy 2.1汉化版：Windows本地文件同步的可控实践

Win11 删除“入门”和“Windows备份”以及 Win10 删除“Windows备份”的方法

如何设置PI-Desktop的思考级别覆盖：为每个模型定制思考深度

更多资讯

CivitAI 的 `dbRead`/`dbWrite` 双客户端路由：当服务层在运行时选择数据库客户端时，测试 mock 如何正确拆分

2026年硕博新生报到须知及新生入校相关注意事项汇总

查aigc免费网站靠谱吗？准确率98.54%的AI率报告带编号可核验，查重报告没有

aigc检测器哪个学校在用？中南大学、湘潭大学等高校AI率查重系统清单

Oracle 11g透明网关访问SQL Server：从安装配置到排错完整指南

STM32CubeMX生成IAR工程实战指南：配置、编译与常见坑

今日更新

AWS无服务器应用开发指南：从Lambda到SAM的架构与实践

SpringBoot+Vue人事系统实战：解决HR数据断点与事务一致性

MATLAB手写紧束缚模型计算石墨烯能带结构

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？