hihoCoder Challenge 29 题解

2 answer(s)

0

请问D题第二句话的函数已i为自变量还是已j为自变量?的斜率递增是怎么回事

0

第二题算是原题吧,https://hihocoder.com/contest/hihointerview22/problem/3

  • 你说的原题,我做了一下,用了简单的字典就能做出来。可是我还是看不懂别人第二题的代码,不明白大多数人代码中的两个状态分别代表什么意思,好忧伤。

  • 我觉得这两题还是不太一样的,希望下面的理解有所帮助 我们用s(i)表示原串中长度为i的前缀所表示的数,如样例"1111", s(1) = 1, s(3) = 7 f[i] 表示获得s(i)的最小操作次数。 a.如果第i+1位是0,那么f[i+1] = f[i] b.如果第i+1位是1,有两种方案: 要么先以f[i]次操作构造出 (s(i)<<1) ,然后加1(需要额外一次操作) 要么先构造出 s(i+1) + 1 , 然后减1, 现在问题是我们不知道构造s(i+1)+1这个数的最少操作次数, 可以发现,s(i+1)+1末位一定是0,在上述情况a中我们已经知道,此时构造s(i+1)+1的操作次数与构造s(i)+1的操作次数是一样的 如构造 s(3)+1 = "1000" = 8 的步数与构造 s(2)+1 = "100" = 4的次数是一样的。 于是记 g[i] 为获得s(i)+1的最小操作次数。 于是有 f[i+1] = min( f[i]+1, g[i]+1 ) 至于g[i]的递推方程,请自行斟酌。 另一种理解方式为g[i]表示向右"借位"的状态。

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享