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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1294][SCOI2009]围豆豆Bean  

2014-10-24 20:32:53|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

奇怪的题……

需要一点计算几何知识

题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<bitset>
#include<map>
using namespace std;
const int N = 10+2;
const int S[5][2] = {{},{0,-1},{0,1},{1,0},{-1,0}};
int n,m,d,data[N],ans;
short Map[N][N];
int scan(){int i=0;scanf("%d",&i);return i;}
char scanc(){char i;scanf(" %c",&i);return i;}
struct state{
int x,y,z;
state(){}
state(int a,int b,int c):x(a),y(b),z(c){}
};
int f[N][N][1024],p[N][2];
short v[N][N][1024],ind[N][N][1024];
queue<state>dui;
int main(){
//freopen("in.txt","r",stdin);
int i,j;char cc;
n = scan();m = scan();
d = scan();
for(i=1;i<=d;i++)data[i] = scan();
for(i=0;i<=n+1;i++)
for(j=0;j<=m+1;j++)
Map[i][j] = -2;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cc = scanc();
if(cc=='0') Map[i][j] = 0;
else if(cc=='#') Map[i][j] = -1;
else{
Map[i][j] = cc-'0';
p[cc-'0'][0] = i;
p[cc-'0'][1] = j;
}
}
}
int bh = 0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(Map[i][j]==0){
bh++;
dui.push(state(i,j,0));
f[i][j][0] = 0;
v[i][j][0] = bh;
while(!dui.empty()){
state next,now = dui.front();dui.pop();
int last = f[now.x][now.y][now.z],add;
if(now.x==i&&now.y==j&&last > ans)ans = last;
for(int k=1;k<=4;k++){
add = 0;
next.x = now.x+S[k][0];next.y = now.y+S[k][1];
if(Map[next.x][next.y] != 0)continue;
if(next.y!=now.y){
bitset<10>tmp(now.z);
state t;
if(now.y > next.y)t = now;
else t = next;
for(int ii=1;ii<=d;ii++){
if(t.y == p[ii][1] && p[ii][0] < t.x){
tmp[ii-1]=tmp[ii-1]^1;
if(tmp[ii-1]) add += data[ii];
else add -= data[ii];
}
}
next.z = tmp.to_ulong();
}else next.z = now.z;
int &fn = f[next.x][next.y][next.z];
short &vn = v[next.x][next.y][next.z],&in = ind[next.x][next.y][next.z];
if(vn!=bh||last-1+add > fn){
fn = last-1+add;
vn=bh;
if(!in){
in = 1;
dui.push(next);
}
}
}
ind[now.x][now.y][now.z] = 0;
}
}
printf("%d\n",ans);
return 0;
}

题解:

状压DP

其实我一开始就看出来是状压DP了

但是状压DP也分好多种

本来觉得以为是插头DP,后来以为是单纯的状压,再后来以为是联通性的状压……

最后总觉得写起来很恶心而且不一定能保证正确,所以就去看题解了,感谢大姐Lavender的指导

然后正解就是单纯的状压

本题最大的难点就是怎么判断豆子是否被围起来了

然后计算几何里有个经典的方法:射线法。

从每个豆子向右作一条射线,然后看这条射线被行进路线穿过的次数是奇数还是偶数,如果是奇数那么就证明一定被围起来了。

所以f[i][j][k]表示现在在(i,j)这个点,围起来豆子的状态是k,bfs记忆化搜索。需要枚举起点

但是现在还有一点问题:走上一条射线接着掉头和穿过去很明显是不同的,但是现在的状态没有办法体现……

再加一维表示上一个方向?

没有那个必要,有一个更好的解决方法:把所有的上下行进路线的线段看做上开下闭的,这样就巧妙地解决了这个问题。

  评论这张
 
阅读(158)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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