[ North American Invitational Programming Contest 2018 ] Flashing Fluorescents

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

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

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


page views : 18 views

发表评论

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