当前位置: 首页 > news >正文

一些dp题

ABC192F

(真的只有绿吗)

首先,很明显有,其中S代表初始魔力值,k为选择的物品数量,x为题目中给定的

然后注意到x很大,但k和n很小,所以我们可以设定状态,表示当前到第i个物品,已经选了j个,总和模k为l,这么选的初始魔法最大值(显然初始魔法越大时间花费越少),然后暴力枚举选的总数量并转移即可,时间复杂度

(oi的精髓在于枚举与模拟)

点击查看代码
void solve() {cin>>n>>x;for(int i=1;i<=n;i++) cin>>a[i];for(int k=1;k<=n;k++) {for(int i=0;i<=n+2;i++)for(int j=0;j<=n+2;j++)for(int l=0;l<=k;l++) dp[i][j][l]=0;for(int i=1;i<=n;i++) { dp[i][1][a[i]%k]=a[i];for(int j=1;j<=n;j++) for(int l=0;l<k;l++) mx(dp[i][j][l],dp[i-1][j][l],dp[i-1][j-1][(l-a[i]%k+k)%k]==0?-inf:dp[i-1][j-1][(l-a[i]%k+k)%k]+a[i]);    } if(dp[n][k][x%k]) ans=min(ans,(x-dp[n][k][x%k])*1ll/k);} printf("%lld",ans);
}
http://www.hskmm.com/?act=detail&tid=23551

相关文章:

  • 【人工智能通识专栏】第三十二讲:本地化部署模型 - 教程
  • [Node.js] chokidar 文件系统监听库
  • Jenkins安装并与GitLab集成,实现dev、qa、uat、prod多分支持续集成的详细步骤 - 指南
  • ZR 2025 十一集训 #1
  • Channel-Driven 降低模块耦合设计复杂度
  • how to download a websites favicon.ico
  • mini-spring实现
  • 10.3
  • Linux 代码利用 STDOUT 打印日志导致应用“假死”?一次线上 Bug 的深度排查与解决
  • 2025 年地坪研磨机公司推荐榜单:盘点 TOP 品牌的格力,宁德时代等标杆客户合作案例
  • Python 新手入门:从零开始学习 Python 的 10 个关键步骤
  • EPL S22 Stage 2 赛前前瞻
  • 计算机类毕业设计开题报告注意事项 - 教程
  • 2025山东设备回收公司 TOP 交易服务推荐排行榜,济宁,梁山设备回收,二手,饮料,食品,制药,实验室,生产线,化工厂,废旧,大型,专业设备回收公司推荐
  • 2025饮料设备回收公司 TOP 交易服务推荐排行榜,济宁,梁山饮料设备回收果汁饮料整厂,饮料生产线,碳酸饮料,乳制品,杀菌机,果汁饮料,二手灌装机,果汁设备回收公司推荐
  • 压力位和支撑位概念
  • 2025 年浙江义乌匹克球拍厂家 TOP 企业品牌推荐排行榜,碳纤维,高级,轻质,定制,高定,比赛专用,玻璃纤维,木制,儿童,匹克球拍套装公司推荐
  • 实用指南:k8s中的schedule
  • 【光照】[PBR][环境光]实现方法解析
  • 树莓派搭建NAS之五:数据同步
  • 初识文件管理
  • 微信社群机器人搭建 教程/开发
  • 2025 年激光粒度仪厂家 TOP 企业品牌推荐排行榜,电位仪 / 纳米粒度及 Zeta 电位仪 / Zeta 电位仪公司推荐
  • 微信智能机器人开发-基于WTAPI框架,实现强大的个微管理
  • 2025粒度仪厂家 TOP 企业品牌推荐排行榜,粒度分析仪,喷雾,激光,纳米,在线,图像粒形,干湿两用粒度仪公司推荐
  • glibc堆
  • 完整教程:从 “T+1” 到 “秒级”:MySQL+Flink+Doris 构建实时数据分析全链路
  • 平均数
  • 质数表
  • 小作业 11