Flashing Fluorescents(状压DP)
Flashing Fluorescents
时间限制: 1 Sec 内存限制: 128 MB
提交: 56 解决: 19
[提交] [状态] [讨论版] [命题人:admin]
题目描述
Pushing a button will affect not just the light in question, but all lights down the line. More specifically, if you choose to press the ith button right before the kth timestep, then the (i + m)th light will toggle on the (k + m)th timestep (with i + m ≤ n). For example, if you press button 5 just before time 19, then light 5 will toggle at time 19, light 6 will toggle at time 20, light 7 will toggle at time 21, and so on. If you push a button that will take effect at the same time as its light would have toggled due to an earlier button press, then the two cancel each other out, including subsequent toggles.
Suppose there are three lights, all of which are off at the start. If you press the first button before the first timestep, this will happen in three timesteps:
Now, suppose you press the first button before the first timestep, and then the second button between the first and second timesteps. The button press will cancel out the propagation, and this will happen (note that the propagation will go no further):
Now, suppose you press the first button before the first timestep, and then the third button between the first and second timesteps. All three lights will be on at the second timestep (but not the third):
You wish to turn on all the lights. What is the earliest time you could possibly see all of the lights turned on? Note that if the lights are all on at time t but not at time t + 1 due to this propagation, t is still the correct answer.
输入
输出
样例输入
1101
样例输出
1
思路:从1开始枚举答案,遍历已经存在的状态,同时加入新的状态,直到所有灯泡变亮,即now=0.
AC代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(<<);
string s;
int n,vis[maxn];
ll cnt,val;
vector<int> v;
int main()
{
cin>>s;
n=s.size();
for(int i=;i<n;i++)
{
if(s[i]=='') val+=(1ll<<i);
}
if(val==)
{
cout<<""<<endl;
return ;
}
vis[val]=;
cnt=(<<n)-;
v.push_back(val);
for(int ans=;;ans++)
{
ll len=v.size();
ll sec=(<<ans)-;
for(int i=;i<len;i++)
{
ll tmp=v[i];
for(int j=;j<=n;j++)
{
ll now=cnt&(tmp^(sec<<j));
if(vis[now]==)
{
vis[now]=;
if(now==)
{
cout<<ans<<endl;
return ;
}
v.push_back(now);
}
}
}
}
return ;
}
最新文章
- js分页小结
- WebAdaptor Object reference not set to an instance of an object.
- [No000014]听说不背单词,考英语会是这种下场-我们为什么必须背单词?
- Android activity跳转方式
- 通过transform属性改变图片的位置大小等信息
- 树 - 从零开始实现by C++
- Android MVP架构分析
- hdu1043Eight (经典的八数码)(康托展开+BFS)
- Elasticsearch .Net Client NEST 索引DataSet数据
- java基础之位运算
- 【Spark篇】--Spark中Standalone的两种提交模式
- Linux 环境 Intelij Idea 安装与快捷图标配置
- Java 平时作业三
- FTP(虚拟用户,并且每个虚拟用户可以具有独立的属性配置)
- FortiGate设置E-mail告警
- Centos 7 下 Corosync + Pacemaker + psc + HA-proxy 实现业务高可用
- Java之逆向工程(1) - 反编译、修补和逆向工程技术 读书笔记
- Locust性能测试2 分布式运行
- centos7修改yum下载源为阿里源
- centos 6.5 python2.6.6 zbar 安装
热门文章
- Win10家庭版组策略gpedit.msc的问题
- $.extend({},defaults, options)
- DOM, DOCUMENT, BOM, WINDOW 有什么区别?
- JavaSE---使用反射生成JDK动态代理
- maya2014无法安装卸载激活失败
- UGUI EventSystem.current.IsPointerOverGameObject(),判断是否进入了UI上
- 性能测试工具LoadRunner30-LR之监控Tomcat
- (转)cut命令详解
- AngularJS directive 动态 template
- intellijidea课程 intellijidea神器使用技巧1-3 idea下载