自动搬运

查看原文

来自洛谷，原作者为

	litc **

搬运于2025-08-24 21:30:31，当前版本为作者最后更新于2013-11-05 21:34:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意：

给定一个01串，要求在一定变换规则的限制下，将其转换成全0串。

考虑如下两个串：

00……0（n个0）——————————（1）

00……01（n-1个0，一个1）—————（2）

设把（1）改成（2）的最小步数为c[n][0]，把（2）改成（1）的最小步数为c[n][1]，则

c[n][0]= c[n][1]=c[n-1][0]+ 1 +c[n-1][1]

方法：把前n-1个由（1）变（2），再改第n个，再由（2）变（1）。

易知c[1][0]=c[1][1]=1，故c[n][0]=c[n][1]=2^n-1

而长度为n的01串至多有2^n个，故串（1）和串（2）是距离最远的01串。

接着，我们设f[n]表示把串的第1位到第n位变为1的最小步数。

如果串的第n位是0，易知有f[n]=f[n-1]

如果串的第n位是1，则我们所需要进行的操作：

1、 把前n-1位变成（2），需要步数为c[n-1][0]-f[n-1]

2、 把第n位变成0，需要1步

3、 把前n-1位变成（1），需要步数为c[n-1][1]

综上，第n位是1时，f[n]=2^n-1-f[n-1]

根据此递推式进行递推即可，注意要加高精。