算法逻辑 / base-superhero-team-sequencing
Advanced

超级英雄团队编排

用有限的四位团队逼近一串数字事件。

思维能力动态规划优化构造

一群数字英雄要依次处理一串数字反派事件。英雄编号和反派编号都是 09。编号越接近,处理这次事件的损害越小;但英雄必须整队出场,所以不能随意逐位挑选英雄。

反派事件序列和英雄出场序列都是数字字符串,且必须保持各自原有的数字顺序。可以在两个字符串中自由插入连字符 -,使它们成为等长的对齐字符串;每个位置至少有一方是数字,不能两方都是连字符。

对齐后的每一列损害如下:

  • 两方都是数字时,英雄数字为 ii、反派数字为 jj,损害为 ij|i-j|
  • 反派数字 jj 对着连字符时,损害为 jj
  • 英雄数字 ii 对着连字符时,损害为 ii

总损害是所有列损害之和。

例如,若反派序列为 271828,英雄序列为 254828,逐位对齐的损害为:

22+57+41+88+22+88=5|2-2|+|5-7|+|4-1|+|8-8|+|2-2|+|8-8|=5

如果将英雄序列对齐为 25-828,则第三列的反派 1 没有英雄处理,损害为 1;总损害反而变成:

22+57+1+88+22+88=3|2-2|+|5-7|+1+|8-8|+|2-2|+|8-8|=3

这说明连字符不是普通字符,而是在“错配损害”和“无人处理的损害”之间作取舍。

英雄只同意作为团队的一部分出场。一个团队是恰好由四个互不相同的数字组成的字符串。例如,团队 0278 一次出场会把 0278 按这个顺序接到英雄序列末尾。你必须选择恰好五个团队;每个团队可以在派遣序列中重复使用任意次数,一名英雄数字也可以属于多个团队。将若干次团队字符串按顺序拼接,就得到英雄数字序列,然后再与反派序列对齐并计算损害。

必答

对下面的反派序列,找出恰好五个四位互异数字团队,以及一种团队派遣顺序,使对齐后的总损害不超过 50

text
31415926535897932384626433832795028841971693993751058209749445923078164

这是 π\pi 的前 71 位数字。

可选奖励

同样使用恰好五个、每个由四个互不相同数字组成的团队,针对下面的反派序列,找出团队派遣顺序和连字符对齐,使总损害不超过 175

text
314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196

这是 π\pi 的前 201 位数字。

输出格式

至少提交必答部分,严格使用三行:

  1. 五个团队字符串组成的列表,例如 ["3945", "0278", "9583", "...", "..."]
  2. 带连字符的反派序列;
  3. 与第二行等长、带连字符的英雄序列。

第二、三行中的连字符位置必须构成实际对齐方案,且两行长度相同。可同时提交奖励部分,但必须清楚标明其三行结果。请给出可核验的总损害,至少说明必答和奖励部分各自的损害。

出题人:xiue