注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[水题][BZOJ1088] [SCOI2005]扫雷Mine  

2014-05-08 08:19:14|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
@[BZOJ1088] [SCOI2005]扫雷Mine

水题

因为只有一列,直接DP即可

#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
const int N = 10000+1;
const int _MAX = 1000000000;
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\n'||cc=='\r')cc=getchar();
if(cc=='+'){fh=1;cc=getchar();}
if(cc=='-'){fh=-1;cc=getchar();}
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}
return re*fh;
}
struct zht{
int i,t;
zht(){}
zht(int ii,int tt):i(ii),t(tt){}
};
int onenum(int x){
int re=0;
for(;x;x>>=1)
if(x&1) re++;
return re;
}
queue<zht> dui;
typedef long long Big;
int n,m,map[N];
Big f[N][8],ans;
int main(){
int i,j;
freopen("input.txt","r",stdin);
n=scan();
for(i=1;i<=n;i++)
map[i]=scan();
dui.push(zht(1,0));
dui.push(zht(1,1));
f[1][0]=1;f[1][1]=1;
while(!dui.empty()){
zht now=dui.front(),next;dui.pop();
next=now;next.i++;next.t=(now.t<<1)&7;
if(now.i==n){
if(onenum(next.t)==map[n]){
ans+=f[now.i][now.t];
}
continue;
}
//0
if(onenum(next.t)==map[now.i]){
if(!f[next.i][next.t])dui.push(next);
f[next.i][next.t]+=f[now.i][now.t];
}
//1
next.t|=1;
if(onenum(next.t)==map[now.i]){
if(!f[next.i][next.t])dui.push(next);
f[next.i][next.t]+=f[now.i][now.t];
}
}
printf("%lld\n",ans);
return 0;
}

其实我觉得这种难度才比较适合我  /w\
  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017