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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

ZOJ3213 基于联通性的状态压缩动态规划  

2013-03-07 15:36:20|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
说真的
独立插头这东西我以前没写过(也许都要省选了却没写过确实是一件比较奇葩的事情,神犇勿嘲讽)
于是一直打算写写的,不过由于代码量比较大,所以一直不是很敢下手,dp的代码量接近300行的话,一般都会有一点畏惧的心理的。
结果就是被某神犇鄙视了——“嘿嘿那你去尝试下BZOJ2755吧。。。包您满意 ZOJ3213 基于联通性的状态压缩动态规划 - hzaskywalker - Yavin(某沙茶的代码库)”!!!
看了看题目,嗯,简单路径,果然爽爽爽!!!
为了以后不被鄙视
所以就决定去试试,但是独立插头还是让人不忍下手。。。
为了降低心理阴影,所以决定选择了ZOJ3212作为练习题。
昨天晚上就开始准备写了。
结果由于唐翔昊大神在打TC,所以就忍不住湊了过去,帮着想了前两题,然后又帮着进行了一下hack。
于是晚上就过去了。
今天早上正式开写——写起来真的很爽,数组爆了也真的很爽。
基本上就是分类讨论。
不过我可是做过TC的男人,这点点分类讨论真的和TC上某些无聊题目比起来还是小菜一叠的。
所以代码很快写好了,不过自然第一遍wrong answer了。。。
然后调啊调,又出去搞了顿饭,回来继续调啊调。。。
尼玛!!!数组开小了。
记得每次写联通dp似乎都有过这样的经验T_T

题意很简单:
n*m的网格,每个格子有个权值,有些格子不能走。求权值最大的一条路径,使得路径的权值和最大
题解:基于联通性的状态压缩动态规划在求解简单路径问题上的应用。

核心思想:写代码一定要写注释。
代码:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;

const int NUM=10;
const int INF=1000000000;
const int P[]={1,1<<2,1<<4,1<<6,1<<8,1<<10,1<<12,1<<14,1<<16};

int n,m,g[NUM][NUM];

inline int get(int a,int k)
{
return a/P[k]%4;
}

inline int revise(int a,int k,int d)
{
return a-get(a,k)*P[k]+d*P[k];
}

int ma[ 1<<18 ][NUM];
int q[1<<18],hash[1<<18],can_be_end[1<<18],num_state;
int f[NUM][NUM][10000];

void update(int& a,int p)
{
if(p>=0 && ( a==-1 || p>a ) )
a=p;
}

#define do(p,w) {if(hash[(p)]!=-1)update(f[i][j][hash[(p)]],(w));if(can_be_end[(p)])ans=max(ans,w);}

void show(int a)
{
int i;
REP2(i,0,m+1)
cout<<get(a,i);
cout<<endl;
}

int change(string a)
{
int ans=0;
for(int i=m;i>=0;--i)
ans=ans*4+a[i]-'0';
return ans;
}

int Main()
{
int i,j,k;
scanf("%d%d",&n,&m);
int ans=0;
REP2(i,0,n)
REP2(j,0,m)
{
scanf("%d",&g[i][j]);
if(g[i][j]==0)
g[i][j]=-INF;
ans=max(ans,g[i][j]);
}
int st[NUM],top;
num_state=0;
memset(hash,-1,sizeof hash);
memset(can_be_end,0,sizeof can_be_end);
REP2(i,0,P[m+1])
{
int num=0;
int flag=1,flag2=0;
top=0;
REP2(j,0,m+1)
{
int p=get(i,j);
if(p==3)
++num;
else if(p==0)
;
else if(p==2)
{
flag2=1;
if(top<=0)
{
flag=0;
break;
}
ma[i][j]=st[--top];
ma[i][ma[i][j]]=j;
}
else st[top++]=j;
}
if(flag && num<=2 && top==0)
{
if(!flag2 && num<=1)
can_be_end[i]=1;
hash[i]=num_state;
q[num_state++]=i;
}
}
memset(f,-1,sizeof f);
f[0][m][hash[0]]=0;
REP(i,1,n)
{
REP2(k,0,num_state)
{
int p=q[k];
if(get(p,m+1)==0)
update(f[i][0][hash[p*4]],f[i-1][m][k]);
}
REP(j,1,m)
{
int w=g[i-1][j-1];
f[i][j][0]=0;
REP2(k,0,num_state)
{
if(f[i][j-1][k]==-1)
continue;
int old=f[i][j-1][k];
int p=q[k],np;
int p1=get(p,j-1),p2=get(p,j);
int oldp=q[k];
p=revise(p,j-1,0);
p=revise(p,j,0);
if(p1==0 && p2==0)
{
//新增左右匹配的插头
np=revise(p,j-1,1);
np=revise(np,j,2);
do(np,old+w);
//跳过
np=p;
if(np)
do(np,old);
//新增独立向下的独立插头
np=revise(p,j-1,3);
do(np,old+w);
//新增独立向右的独立插头
np=revise(p,j,3);
do(np,old+w);
}
else if(p1!=3 && p2!=3)
{
if(p1 && p2)//不可能有独立插头
{
if(p1==p2)//只能连起来
{
if(p1==2)
{
np=revise(p,ma[oldp][j-1],2);
do(np,old+w);
}
else if(p1==1)
{
np=revise(p,ma[oldp][j],1);
do(np,old+w);
}
}
else if(p1==2 && p2==1)//可以连起来
{
np=p;
do(np,old+w);
}
else //1,2的话,那么就形成了回路,应该可以连起来,特判更新答案
{
if(p==0)//更新答案
update(ans,old+w);
//注意1,2是不能连起来的
}
}
else
{
int u=p1?p1:p2;//两种情况似乎可以合并
//上面有东西,作为傻叉,我可以将其继续
//往下连
np=revise(p,j-1,u);
do(np,old+w);
//拐了个弯
np=revise(p,j,u);
do(np,old+w);
//封住
if(p2)//往下的封住了
{
np=revise(p,ma[oldp][j],3);//相连的那个成了可怜的独立插头
do(np,w+old);
}
else
{
np=revise(p,ma[oldp][j-1],3);//同上
do(np,w+old);
}
}
}
else //现在肯定有了个独立插头,yy开始
{
if(p1==3 && p2==3)//两个独立插头,如果连起来的话就结束算法,找到答案。
{
if(!p)
update(ans,old+w);
}
else if(!p1 || !p2)//只有一个独立插头
{
//首先似乎可以更新答案
if(!p)//封住了
update(ans,old+w);
//然后可以往下或往右拓展
//往下连
np=revise(p,j-1,3);
do(np,old+w);
//拐了个弯
np=revise(p,j,3);
do(np,old+w);
}
else //另一个插头会与独立插头相连,于是修改另一边为独立插头
{
if(p1==3)
{
np=revise(p,ma[oldp][j],3);
do(np,old+w);
}
else
{
np=revise(p,ma[oldp][j-1],3);
do(np,old+w);
}
}
}
}
}
}
cout<<ans<<endl;
return 0;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int T;
scanf("%d",&T);
while(T--)
Main();
return 0;
}




  评论这张
 
阅读(559)| 评论(1)
推荐 转载

历史上的今天

评论

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

页脚

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