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

ydc的博客

 
 
 

日志

 
 

ZOJ3213 独立插头DP  

2013-05-19 17:45:41|  分类: 模板 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
真的是自信满满的开始写这道题
觉得自己连平面图都写过了,三百行左右的数据结构题也写过,这一个不到三百行的DP应该不会有太大问题吧。
结果写了一天多……去掉所有颓的时间还是写了一天
刚开始的时候看cdq的论文,然后没注意到那道题每个点恰好经过一次竟然不小心把那篇文章里面“这种情况只能发生在最后一个非障碍格子“的限制条件给写进了if!!
傻叉了……
然后继续调啊调啊调
无数次想放弃了……

终于最后搞出来了
的确如我所料是二逼错误
而且是平常很少犯的二逼错误
可为什么平常很少犯的二逼错误,竟然在这种长代码上犯了呢??
感觉一开始思路好清晰的
但是等真正调出来的时候才发现有二逼错误出现了
代码量一大,平常少犯的错就犯了。
结果就被这题弄得筋疲力尽
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 10
#define maxs 265000
using namespace std;
int pos[maxs];
int queue[maxs],F[2][maxs],next[maxs][maxn];
int n,m,map[maxn][maxn],tot;
bool canend[maxs];
int get(int p,int k)
{
	return p>>(k<<1)&3;
}
int calc(int p,int k)
{
	return p<<(k<<1);
}
void read()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&map[i][j]);
	memset(canend,false,sizeof(canend));
	memset(pos,0,sizeof(pos));
	tot=0;
}
void Prepare()
{
	static int stack[maxn],temp[maxn];
	for(int i=0;i<calc(1,m+1);i++)
	{
		int top=0,cnt=0;
		bool mark=true,flag=true;
		memset(temp,0,sizeof(temp));
		for(int j=0;j<=m&&mark;j++)
		{
			int p=get(i,j);
			if(p==1)
			{
				flag=false;
				stack[++top]=j;
			}
			else if(p==2&&top==0)
				mark=false;
			else if(p==2)
			{
				temp[j]=stack[top];
				temp[stack[top--]]=j;
			}
			else if(p==3&&cnt==2)
				mark=false;
			else if(p==3)
				cnt++;
		}
		if(top!=0||mark==false)
			continue;
		queue[++tot]=i;
		pos[i]=tot;
		for(int j=0;j<=m;j++)
			next[tot][j]=temp[j];
		if(flag==true&&cnt<=1)
			canend[tot]=true;
	}
}
int Dp()
{
	int cur=0,ans=-1;
	for(int i=1;i<=tot;i++)
		F[cur][i]=-1;
	F[cur][pos[0]]=0;
	for(int i=1;i<=n;i++)
	{
		cur^=1;
		for(int j=1;j<=tot;j++)
			F[cur][j]=-1;
		for(int j=1;j<=tot;j++)
			if(get(queue[j],m)==0)
				F[cur][pos[queue[j]<<2]]=F[cur^1][j];
		for(int j=1;j<=m;j++)
		{
			cur^=1;
			for(int k=1;k<=tot;k++)
				F[cur][k]=-1;
			for(int k=1;k<=tot;k++)
			{
				/* x是左插头,y是上插头 */
				int p=queue[k],x=get(p,j-1),y=get(p,j);
				if(F[cur^1][k]==-1)
					continue;
				/* 没有左插头和上插头 */
				if(x==0&&y==0)
				{
					/* 不走 */
					if((j!=m||get(queue[k],m)==0)&&k)
						F[cur][k]=max(F[cur][k],F[cur^1][k]);
					/* 可以走 */
					if(map[i][j]!=0)
					{
						ans=max(ans,map[i][j]);
						int newp;
						newp=pos[p^calc(1,j-1)^calc(2,j)];
						if(j!=m||get(queue[newp],m)==0)
							F[cur][newp]=max(F[cur][newp],F[cur^1][k]+map[i][j]);
						/* 新建一个下插头 */
						newp=pos[p^calc(3,j-1)];
						if((j!=m||get(queue[newp],m)==0)&&newp)
							F[cur][newp]=max(F[cur][newp],F[cur^1][k]+map[i][j]);
						/* 新建一个右插头 */
						newp=pos[p^calc(3,j)];
						if(j!=m||get(queue[newp],m)==0)
							F[cur][newp]=max(F[cur][newp],F[cur^1][k]+map[i][j]);
					}
				}
				if(map[i][j]==0)
					continue;
				/* 只有左插头 */
				if(x!=0&&y==0)
				{
					/* 它是一个独立插头 */
					if(x==3)
					{
						/* 此时可以更新答案 */
						if((p^calc(x,j-1))==0)
							ans=max(ans,F[cur^1][k]+map[i][j]);
						/* 向下延续独立插头 */
						if(j!=m||get(queue[k],m)==0)
							F[cur][k]=max(F[cur][k],F[cur^1][k]+map[i][j]);
						/* 向右延续独立插头 */
						int newp=pos[p^calc(3,j-1)^calc(3,j)];
						if(j!=m||get(queue[newp],m)==0)
							F[cur][newp]=max(F[cur][newp],F[cur^1][k]+map[i][j]);
					}
					/* 否则就是普通的插头DP */
					else
					{
						/*拐弯*/
						if((j!=m||get(queue[k],m)==0)&&k)
							F[cur][k]=max(F[cur][k],F[cur^1][k]+map[i][j]);
						/*向右走*/
						int newp;
						newp=pos[p^calc(x,j-1)^calc(x,j)];
						if(j!=m||get(queue[newp],m)==0)
							F[cur][newp]=max(F[cur][newp],F[cur^1][k]+map[i][j]);
						/*封死,这一步是特有的*/
						newp=pos[p^calc(x,j-1)^calc(x,next[k][j-1])];
						if(j!=m||get(queue[newp],m)==0)
							F[cur][newp]=max(F[cur][newp],F[cur^1][k]+map[i][j]);
					}
				}
				/* 只有上插头 */
				if(x==0&&y!=0)
				{
					/* 它是一个独立插头 */
					if(y==3)
					{
						/* 此时可以更新答案 */
						if(canend[k])
							ans=max(ans,F[cur^1][k]+map[i][j]);
						/* 向右延续独立插头 */
						if(j!=m||get(queue[k],m)==0)
							F[cur][k]=max(F[cur][k],F[cur^1][k]+map[i][j]);
						/* 向下延续独立插头 */
						int newp=pos[p^calc(3,j-1)^calc(3,j)];
						if((j!=m||get(queue[newp],m)==0)&&newp)
							F[cur][newp]=max(F[cur][newp],F[cur^1][k]+map[i][j]);
					}
					/* 否则就是普通的插头DP */
					else
					{
						/*拐弯*/
						if(j!=m||get(queue[k],m)==0)
							F[cur][k]=max(F[cur][k],F[cur^1][k]+map[i][j]);
						/*向下走*/
						int newp;
						newp=pos[p^calc(y,j-1)^calc(y,j)];
						if(j!=m||get(queue[newp],m)==0)
							F[cur][newp]=max(F[cur][newp],F[cur^1][k]+map[i][j]);
						/*封死,这一步是特有的*/
						newp=pos[p^calc(y,j)^calc(y,next[k][j])];
						if(j!=m||get(queue[newp],m)==0)
							F[cur][newp]=max(F[cur][newp],F[cur^1][k]+map[i][j]);
					}
				}
				p=p^calc(x,j-1)^calc(y,j);
				/* 两个都是独立插头,合并他们 */
				if(x==3&&y==3)
				{
					if(p==0)
						ans=max(ans,F[cur^1][k]+map[i][j]);
				}
				/* 只有左边是个独立插头 */
				else if(x==3&&y!=0)
				{
					int newp=pos[p^calc(y,next[k][j])];
					if(j!=m||get(queue[newp],m)==0)
						F[cur][newp]=max(F[cur][newp],F[cur^1][k]+map[i][j]);
				}
				/* 只有右边是个独立插头 */
				else if(x!=0&&y==3)
				{
					int newp=pos[p^calc(x,next[k][j-1])];
					if(j!=m||get(queue[newp],m)==0)
						F[cur][newp]=max(F[cur][newp],F[cur^1][k]+map[i][j]);
				}
				/* 此时是普通的插头DP */
				else
				{
					if(x==1&&y==1)
					{
						int newp=pos[p^calc(3,next[k][j])];
						if(j!=m||get(queue[newp],m)==0)
							F[cur][newp]=max(F[cur][newp],F[cur^1][k]+map[i][j]);
					}
					if(x==2&&y==2)
					{
						int newp=pos[p^calc(3,next[k][j-1])];
						if(j!=m||get(queue[newp],m)==0)
							F[cur][newp]=max(F[cur][newp],F[cur^1][k]+map[i][j]);
					}
					if(x==1&&y==2&&p==0)
						ans=max(ans,F[cur^1][k]+map[i][j]);
					if(x==2&&y==1)
					{
						if(j!=m||get(queue[pos[p]],m)==0)
							F[cur][pos[p]]=max(F[cur][pos[p]],F[cur^1][k]+map[i][j]);
					}
				}
			}
		}
	}
	return ans==-1?0:ans;
}
int main()
{
	int test;
	for(scanf("%d",&test);test;test--)
	{
		read();
		Prepare();
		printf("%d\n",Dp());
	}
	return 0;
}


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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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