AcWing--保险箱-->dp

这篇具有很好参考价值的文章主要介绍了AcWing--保险箱-->dp。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

5408. 保险箱 - AcWing题库(python)

# 操作顺序不影响操作结果
# 从右往左进行操作 对于某一位操作时不会影响右边结果


# 输入
n=int(input())
a=list(map(int,input()))
b=list(map(int,input()))
# 创建dp列表
f=list([float('inf') for _ in range(3)] for _ in range(n+1))
f[n][1]=0

# dp状态 枚举每一次操作 每一次操作三种状态
# 从右往左
for i in range(n-1,-1,-1):
    # 每一次三种操作
    for j in range(3):
        for k in range (-9,10):
            for t in range(3):
                if a[i]+k+t-1-b[i]==(j-1)*10:
                    f[i][j]=min(f[i][j],f[i+1][t]+abs(k))
result = min(f[0][0], f[0][1], f[0][2])
print(result)
 文章来源地址https://www.toymoban.com/news/detail-802966.html

到了这里,关于AcWing--保险箱-->dp的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • acwing算法基础之动态规划--数位统计DP、状态压缩DP、树形DP和记忆化搜索

    暂无。。。 暂无。。。 题目1 :求a~b中数字0、数字1、…、数字9出现的次数。 思路:先计算1~a中每位数字出现的次数,然后计算1~b-1中每位数字出现的次数,两个相减即是最终答案。 那么,如何计算1~a中每位数字出现的次数呢? 首先,将a的每一位存入向量num中,例如a=123

    2024年02月04日
    浏览(51)
  • AcWing算法学习笔记:动态规划(背包 + 线性dp + 区间dp + 计数dp + 状态压缩dp + 树形dp + 记忆化搜索)

    算法 复杂度 时间复杂度0(nm) 空间复杂度0(nv) 代码 算法 通过滚动数组对01背包朴素版进行空间上的优化 f[i] 与 f[i - 1]轮流交替 若体积从小到大进行遍历,当更新f[i, j]时,f[i - 1, j - vi] 已经在更新f[i, j - vi]时被更新了 因此体积需要从大到小进行遍历,当更新f[i, j]时,f[i - 1,

    2024年02月21日
    浏览(43)
  • 北邮22级信通院数电:Verilog-FPGA(5)第四第五周实验 密码保险箱的设计

    北邮22信通一枚~ 跟随课程进度更新北邮信通院数字系统设计的笔记、代码和文章 持续关注作者 迎接数电实验学习~ 获取更多文章,请访问专栏: 北邮22级信通院数电实验_青山如墨雨如画的博客-CSDN博客 目录 一.密码箱的功能和安全性 显示: 输入部分: 确认键: 复位键:

    2024年02月08日
    浏览(46)
  • Acwing.901 滑雪(动态规划)

    给定一个R行C列的矩阵,表示一个矩形网格滑雪场。 矩阵中第i行第j列的点表示滑雪场的第i行第j列区域的高度。 一个人从滑雪场中的某个区域内出发,每次可以向上下左右任意一个方向滑动一个单位距离。当然,一个人能够滑动到某相邻区域的前提是该区域的高度低于自己

    2024年02月15日
    浏览(49)
  • Acwing.285 没有上司的舞会(动态规划)

    Ural大学有N名职员,编号为1~N。 他们的关系就像—棵以校长为根的树,父节点就是子节点的直接上司。每个职员有一个快乐指数,用整数H给出,其中1≤i≤N。 现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。 在满足这个条件的前提下,主办方希望邀请

    2024年02月15日
    浏览(75)
  • C++算法之动态规划(ACWING题目)

    动态规划时间复杂度:状态数量*转移计算量 线性DP 一.数字三角形 动态规划:     1.状态表示:         集合:f[i, j]表示所有从起点走到(i, j)的路径         属性:所有路径上的数字之和的最大值     2.状态计算:         如何得到f[i, j]?             从左边路径走到和

    2024年02月20日
    浏览(42)
  • acwing算法基础之动态规划--背包问题

    (零) 背包问题描述:有 N N N 个物品,每个物品的体积是 v i v_i v i ​ ,价值是 w i w_i w i ​ ,现有容量是 V V V 的背包,求这个背包能装下的物品的最大价值。 01背包问题:每个物品只有1个。 完全背包问题:每个物品有无穷多个。 多重背包问题:第 i i i 个物品有 s i s_i s

    2024年02月05日
    浏览(47)
  • Acwing.291 蒙德里安的梦想(动态规划)

    求把N M的棋盘分割成若干个1 2的的长方形,有多少种方案。 例如当N=2,M=4时,共有5种方案。当N=2,M=3时,共有3种方案。如下图所示: 输入包含多组测试用例。 每组测试用例占一行,包含两个整数N和M。 当输入用例N=0,M=0时,表示输入终止,且该用例无需处理。 每个测试用例

    2024年02月15日
    浏览(38)
  • Acwing.91 最短Hamilton路径(动态规划)

    给定一张n个点的带权无向图,点从0~n-1标号,求起点0到终点n-1的最短Hamilton路径。Hamilton路径的定义是从0到n-1不重不漏地经过每个点恰好一次。 第—行输入整数n。 接下来n行每行n个整数,其中第i行第j个整数表示点i到j的距离(记为a[i.i])。对于任意的, y,z,数据保证a[x,x]=0,

    2024年02月15日
    浏览(44)
  • Acwing-基础算法课笔记之动态规划(背包问题)

    01背包中的0和1指的是放与不放,而且不能出现放多个的情况,背包只能放相同物品中的一个; 首先是对 d [ i ] [ j ] d[i][j] d [ i ] [ j ] 数组的解释,该数组表示的是只看前 i i i 个物品,总体积是 j j j 的情况下,总价值最大是多少; 不选第 i i i 个物品,只考虑前 i − 1 i-1 i −

    2024年04月17日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包