手机扫描二维码下载客户端
专辑: 未知 The Walking 发行时间: 上传时间 歌曲来源: 酷我主播电台UGC平台
北京酷我科技有限公司版权所有 丨 网络文化经营许可证: 丨 丨 增值电信业务经营許可证B2- 丨
举报电话:010-丨 举报邮箱:
去首页 添加自己喜欢的歌曲吧~
题意:给出两个数字位数相同汾别中间有若干位不知道,用问号表示现在要求补全这两个数字,使得差值的绝对值最小多解则取第一个数字的值最小的,再多解就取第二个数字最小的
类似数位dp,但是很多状态可以直接得出最终解个别状态需要状态转移。
我们从高位到低位依次确定两个数的每个位是几一旦确定了两个数的一个位不一样,则可以立即将小的一方的后续问号全部写9大的一方后续问号全部写0。这样才能让差值最小
那我们观察每个位的时候要如何确定其值呢?分如下几种情况
1.两个数的该位都是问号,那么分三种情况:
1.1 都标为0看下一个位。
1.2&1.3 将一位标为1另一个位标为0,并更新答案终结状态。(这表示我们主动在高位制造了一个差值以便后面取得整体差值最小例如:?0,9?答案是100,099)
2.两个数的该位都不是问号,若相等继续看下一位。若不等则标出后面问号,更新答案终结状态。
3.两个数的该位有一个是问号那么这个这与第一种情况类似,分三种情况处理
3.1 标为与该位相等,看下一个位
3.2 标为该位减1,赋值后续问号更新答案,终结状态
3.3 标为该位加1,赋值后续问号更新答案,终结状态
就这么多情况。值得注意的是虽然有些时候进行了状態转移(看下一个位)。但是并不需要搜索和回溯因为每个状态的多个分支中,只有一个是状态转移其他的都是最终态。