题解 P1805 【关灯】
题目大意：
给定一个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]
根据此递推式进行递推即可，注意要加高精。