题目大意:有n盏灯\( ( 1 \leq n \leq 16 ) \),编号为1到n,每一秒可以按下某一盏灯的开关。如果在某时刻\(t\)按下第\(i\)盏灯的开关,第t+k时刻第i+k盏灯的状态就会被改变。现给出n盏灯的初始状态,求至少要多久灯才会全部变亮。

题解:考虑每个操作对灯状态的影响,用01来表示灯的灭和亮两个状态,可以发现每个操作相当于对灯的某一区间取反。另外答案一定小于等于n。

枚举答案,然后对状态进行一次长度为ans的操作(这里进行的操作实际上是从刚开始就进行的,并不是枚举第ans时刻在哪个位置按下开关),状压DP即可。

#include <bits/stdc++.h>
using namespace std;

char ch[20];
int f[20][1<<16];
int State;
int n,ans,k;

int main()
{
	scanf("%s",ch);
	n=strlen(ch);
	k=(1<<n)-1;
	for (int i=n-1;i>=0;i--) (State<<=1)|=ch[i]-'0';
	f[0][State]=1;
	while (!f[ans][k])
	{
		ans++;
		for (int i=0;i<=k;i++) f[ans][i]=f[ans-1][i];
		for (int o=0;o<=k;o++) if (f[ans-1][o])
		for (int i=0;i<n;i++)
		{
			int mask=(((1ll<<(i+ans))-1)^((1ll<<i)-1))&k;
			f[ans][o^mask]=1;
		}
	}
	printf("%d\n",ans);
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注