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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1187][HNOI2007]神奇游乐园  

2014-11-24 22:00:10|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1187: [HNOI2007]神奇游乐园

插头DP复习……
写了半晚上调了半晚上,代码能力越来越弱了
顺便感谢lzr神犇的指导
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 100+10;
const int M = 10;
const int L = 3000*10+10;
int scan(){int i=0;scanf("%d",&i);return i;}
int n,m,ans = -2e9;
short Map[N][M],go[N][M];
int f[2][L],v[2][L];
struct State{
int i,j,bh;
int d(){return (i-1)*m+j;}
State(int a,int b,int c):i(a),j(b),bh(c){}
};
queue<State>dui;
short list[M];
void listit(int bh,short a[]){for(int i=1;i<=m+1;i++,bh/=3)a[i]=bh%3;}
int zip(short a[]){int re=0;for(int i=m+1;i;i--)re=re*3+a[i];return re;}
int count(){int re=0;for(int i=1;i<=m+1;i++)if(list[i])re++;return re;}
void maintain(int p,int type,short a[]){
int cot=0,i;
if(type==2){
for(i=p;i<=m+1;i++){
if(a[i]==1)cot++;
if(a[i]==2)cot--;
if(cot<0)break;
}a[i] = 1;

}else{
for(i=p;i;i--){
if(a[i]==2)cot++;
if(a[i]==1)cot--;
if(cot<0)break;
}a[i] = 2;
}
}
void update(int last,State next,int val){
if(last!=0&&next.bh==0){ans = max(ans,val);return;}
int &fn = f[next.d()%2][next.bh]
,&vn = v[next.d()%2][next.bh];
if(vn!=next.d()){
vn = next.d();
fn=val;
dui.push(next);
}else fn = max(fn, val);
}
bool chatou(int i,int j,int type){
if((type&1) && go[i+1][j])return 0;
if((type&2) && go[i][j+1])return 0;
return 1;
}
int main(){
//freopen("in.txt","r",stdin);
int i,j;
n = scan();m = scan();
for(i=1;i<=n;i++)go[i][0]=go[i][m+1]=1;
for(i=1;i<=m;i++)go[0][i]=go[n+1][i]=1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
Map[i][j] = scan();
dui.push(State(1,1,0));
while(!dui.empty()){
State now = dui.front(),next(0,0,0);dui.pop();
int &last = f[now.d()%2][now.bh],val = Map[now.i][now.j];
if(now.j==1)now.bh = now.bh*3;
next=now;i = now.j;
next.j++;
if(next.j>m)next.j=1,next.i++;
if(now.i>n)continue;
listit(now.bh,list);
/*
if(now.i==2 && now.j==2 && list[1]==1 && list[2]==0 && list[3]==0 && list[4]==2){
//if(now.i==2 && now.j==1 && now.bh==57*3){
printf("[1]%d\n",last);
}
if(now.i==2 && now.j==3 && list[1]==1 && list[2]==1 && list[3]==2 && list[4]==2){
//if(now.i==2 && now.j==1 && now.bh==57*3){
printf("[2]%d\n",last);
}*/
/*
if(now.i==2 && now.j==3 && now.bh==76){
//if(now.i==2 && now.j==1 && now.bh==57*3){
printf("[2]%d\n",last);
}*/
if(list[i]==list[i+1]&&list[i]==0){
//ignore
//next.bh = zip(list);
update(now.bh,next,last);
//make a new
if(chatou(now.i,now.j,3)){
list[i]=1;list[i+1]=2;
next.bh = zip(list);
update(now.bh,next,last+val);
}
}
else if(list[i]==list[i+1]&&list[i]>0){
//listit(now.bh,list);
if(list[i] == 1)maintain(i+1+1,2,list);
else maintain(i-1,1,list);
list[i]=list[i+1]=0;
next.bh = zip(list);
update(now.bh,next,last + val);
}
else if(list[i]*list[i+1]==0 && list[i]+list[i+1]>0){
if(chatou(now.i,now.j,1)){
listit(now.bh,list);
if(!list[i])swap(list[i+1],list[i]);
next.bh = zip(list);
update(now.bh,next,last+val);
}
if(chatou(now.i,now.j,2)){
listit(now.bh,list);
if(!list[i+1])swap(list[i+1],list[i]);
next.bh = zip(list);
update(now.bh,next,last+val);
}
}
else if(list[i]*list[i+1]>0&&list[i]!=list[i+1]){
//listit(now.bh,list);
if(list[i]==1&&list[i+1]==2&&count()>2)continue;
list[i] = list[i+1] = 0;
next.bh = zip(list);
update(now.bh,next,last+val);
}
}
printf("%d\n",ans);
return 0;
}

题解:
插头DP
第一次写不是全走的插头DP
不太会写,一开始写完了结果发现可能出现多个环……
然后去请教lzr神犇
和一般插头DP不同的地方(广义括号法):
1.可以在任何地方放空格子,在任何位置开始
2.合并一个左右插头仅当状态中只有这两个插头,这时需要更新答案并且不再向下转移
  评论这张
 
阅读(70)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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