P1805 关灯 题解

P1805 关灯 题解

很明显的递推题，但是高精度。

解法

相信大家都对九连环的游戏有所了解。如果不拆除前面的环，那后面的环也就不能拆除。有依赖关系。

考虑设置状态。

题中要求所有灯全部熄灭所用的步数，所以这里设置状态 $f$，$f_i$ 表示前 $i$ 盏灯全部熄灭所用的最少步数。由于第 $i$ 盏灯可以被操作的前提是前 $i-1$ 盏灯满足一定条件，所以只能从左到右顺序操作。现在考虑如何转移。

如果第 $i$ 盏灯本来就是灭的。那这个位置不用操作，$f_i=f_{i-1}$。

如果第 $i$ 盏灯本来是亮的，那这个位置需要操作。此时已经处理了前 $i-1$ 盏灯的情况。这里分两种情况讨论。

为了辅助这个过程，我们再设一个状态 $g$，$g_i$ 表示在前 $i$ 盏灯全部熄灭的情况下点亮第 $i$ 盏灯所用的最少步数，这里等价于前 $i-1$ 盏灯全部熄灭、第 $i$ 盏灯点亮的情况下使前 $i$ 盏灯全部熄灭所用的最少步数。题中说编号为 $1$ 的灯可以随意开或关，所以 $g_1=1$。考虑 $g_2$。$g_2$ 即为开 $1$，开 $2$，关 $1$ 的最少步数，即为 $g_1\times 2+1$。考虑 $g_i$，即为开 $i-1$，开 $i$，关 $i-1$ 的最少步数，即为 $g_i-1\times 2+1$。利用数学归纳法：

$$\begin{array}{rl}& g_1=1=2^1-1\\ & g_2=g_1\times 2+1=(2^1-1)\times 2+1=2^1+1=2^2-1\\ & g_3=g_2\times 2+1=(2^2-1)\times 2+1=2^3-2+1=2^3-1\\ & g_i=g_{i-1}\times 2+1=(2^{i-1}-1)\times 2+1=2^i-2+1=2^i-1\end{array}$$

得出结论：$g_i=2^i-1$。

• 如果第 $i-1$ 盏灯本来是亮的。则 $f_i=g_{i-1}-f_{i-1}+1+g_{i-1}=g_i-f_{i-1}$。
• 如果第 $i-1$ 盏灯本来是熄灭的的。则 $f_i=g_{i-1}-f_{i-2}+1+g_{i-1}=g_{i-1}-f_{i-2}+1+gi-1=g_i-f_{i-2}=g_i-f_{i-1}$。

综上，$f_i=\{\begin{array}{ll}{f}_{i-1}& a_i=0\\ g_i-f_{i-1}& a_i=1\end{array}$。

高精度略。

代码

#include<bits/stdc++.h>
template <typename T>
inline void swap(T &x,T &y)
{
	T tmp=x;
	x=y,y=tmp;
}
class high_accuracy
{
private:
	int len,a[5000];
public:
	inline int &operator[](const int &x)
	{
		return a[x];
	}
	inline int size()
	{
		return len;
	}
	inline high_accuracy()
	{
		len=0,a[0]=a[1]=a[2]=0;
	}
	inline void init(__int128 x)
	{
		len=0;
		if(x==0) len=1,a[1]=0;
		while(x) a[++len]=x%10,x/=10;
	}
	inline void deal(int l)
	{
		for(int i=1;i<=l;i++)
		{
			while(a[i]<0) a[i+1]--,a[i]+=10;
			a[i+1]+=a[i]/10,a[i]%=10;
		}
		len=l;
		while(!a[len]) len--;
	}
	inline void print()
	{
		for(int i=std::max(len,1);i;i--) std::cout<<a[i];
		std::cout<<"\n";
	}
	inline high_accuracy operator+(high_accuracy rhs)
	{
		high_accuracy ret;
		int le=std::max(len,rhs.size());
		for(int i=1;i<=le+3;i++) ret[i]=0;
		for(int i=1;i<=le;i++) ret[i]+=a[i]+rhs[i];
		ret.deal(le+2);
		return ret;
	}
	inline high_accuracy operator-(high_accuracy rhs) // 适用于 *this 比 rhs 大的情况
	{
		high_accuracy ret;
		int le=std::max(len,rhs.size());
		for(int i=1;i<=le+3;i++) ret[i]=0;
		for(int i=1;i<=le;i++) ret[i]+=a[i]-rhs[i];
		ret.deal(le+2);
		return ret;
	}
	inline high_accuracy operator*(high_accuracy rhs)
	{
		high_accuracy ret;
		for(int i=1;i<=len+rhs.size()+5;i++) ret[i]=0;
		for(int i=1;i<=len;i++) for(int j=1;j<=rhs.size();j++) ret[i+j-1]+=a[i]*rhs[j];
		ret.deal(len+rhs.size()+5);
		return ret;
	}
};
high_accuracy f[1010],pw[1010];
int n,a[1010];
int main()
{
	std::cin>>n,pw[0].init(1),pw[1].init(2),f[0].init(0);
	for(int i=1;i<=n;i++) std::cin>>a[i];
	for(int i=2;i<=n;i++) pw[i]=pw[i-1]*pw[1];
	if(a[1]) f[1].init(1);
	for(int i=2;i<=n;i++)
		if(a[i]) f[i]=pw[i]-pw[0]-f[i-1];
		else f[i]=f[i-1];
	f[n].print();
	return 0;
}