相邻字符连续删除的场景,这是一个典型的栈的应用。
所以用栈这么操作后,在栈中的元素必然是 101010... 或者 010101... 这样的
这部分元素我们考虑修改,现在令栈中的元素构成的串为 t 。
t 的长度为偶数,则修改 2t 个即可。
小蓝有一个仅由数字 0 和 1 组成的字符串,他发现可以对这个字符串进行一种消除操作:
如果字符串中存在相邻且相同的两个数字,这两个数字会同时消失,剩下的部分会拼接成新的字符串。之后不断重复这一过程,直到字符串中任意相邻的两个数字都不相同。我们称这个过程为“充分消除”。
现在,小蓝获得了恰好 k 次翻转机会。每次翻转可以选择字符串中的任意一个位置,将该位置的数字改变:0 变为 1,或者 1 变为 0。同一个位置也可以被多次翻转。
小蓝想知道,在必须用完这 k 次翻转的前提下,如何规划翻转的位置,才能使得翻转后的字符串经过充分消除,最终得到的字符串长度尽可能短。请你帮他求出这个最短的长度。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册