首页 > 其他分享 >P3190 [HNOI2007]神奇游乐园

P3190 [HNOI2007]神奇游乐园

时间:2023-03-31 17:44:57浏览次数:59  
标签:ch P3190 游乐园 int HNOI2007 getchar define

P3190 [HNOI2007]神奇游乐园

用\(unordered\_map\)有个坑,写在了下面这个博客

https://www.luogu.com.cn/blog/zhouzhuo/gei-yong-unorderedmap-di-hou-ren-ti-gong-dai-ma

再贴一下代码吧

点击查看代码
#include<bits/stdc++.h>
#include<unordered_map>
#define int long long
#define inf 1e18
#define inc 0xcfcfcfcf
#define N 107
#define M 17
#define mod 1000000007
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
using namespace std;
int T=1,n,m,ex,ey;
int ans=-inf; 
int g[N][M];
unordered_map<int,int> f[2];
inline int Read()
{
	char ch=getchar();bool f=0;int x=0;
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	if(f==1)x=-x;return x;
}
int Get_s(int num,int pos){return (num<<(pos<<1));}//得到第pos位为num的四进制 
void Insert(int pos,int S,int val)
{
	if(f[pos].find(S)==f[pos].end())
		f[pos][S]=val;
	else
		f[pos][S]=max(f[pos][S],val);
}
void Ctdp()
{
	int now=0;
	int mxn=(1<<((m+1)<<1))-1;//m+1位全为3的四进制码,方便后面截去m+1位之后的数 
	f[now][0]=0; 
	f[now^1].clear();
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			int nxt=now^1;
			for(auto k:f[now])
			{
			//printf("(%lld,%lld)qwq\n",i,j);
				int S=k.first,val=k.second;  
				int ctl=(S>>((j-1)<<1))&3,ctr=(S>>(j<<1))&3;//ctl表示当前格子第一个插头,为1表示左插头,2为右插头,ctr类似
				//下面为当前格子必须放置插头
				if(!ctl&&!ctr)//若本来无插头进入 
				{
					Insert(nxt,S,val);
					if(j!=m&&i!=n)//可以新建两个插头 
						Insert(nxt,S^Get_s(1,j-1)^Get_s(2,j),val+g[i][j]);
				}
				if(!ctl&&ctr)//若只有第二个插头,可转移到下方和右方 
				{
					if(i!=n)
					    Insert(nxt,S^Get_s(ctr,j-1)^Get_s(ctr,j),val+g[i][j]);
					if(j!=m)
						Insert(nxt,S,val+g[i][j]);
				}
				if(ctl&&!ctr)//若只有第一个插头,也类似地可转移到下方和右方 
				{
					if(j!=m)
					    Insert(nxt,S^Get_s(ctl,j-1)^Get_s(ctl,j),val+g[i][j]);
					if(i!=n)
						Insert(nxt,S,val+g[i][j]);
				}
				//下面为两个插头都存在 
				if(ctl==ctr)//两个插头性质相同 
				{
					if(ctl==1)//如果都为左插头,则右边最近的一个右插头要变为左插头 
					{
						int cnt=1;
						for(int p=j+1;;++p)
						{
							int pos=(S>>(p<<1))&3;
							if(pos==1) ++cnt;
							if(pos==2) --cnt;
							if(cnt==0)
							{
								Insert(nxt,S^Get_s(ctl,j-1)^Get_s(ctr,j)^Get_s(2,p)^Get_s(1,p),val+g[i][j]);
								break;
							}	
						}
					}
					if(ctl==2)//如果都是右插头,则左边最近的左插头要变为右插头 
					{
						int cnt=1;
						for(int p=j-2;;--p)
						{
							int pos=(S>>(p<<1))&3;
							if(pos==2) ++cnt;
							if(pos==1) --cnt;
							if(cnt==0)
							{
								Insert(nxt,S^Get_s(ctl,j-1)^Get_s(ctr,j)^Get_s(2,p)^Get_s(1,p),val+g[i][j]);
								break;
							}	
						}
					}
				}
				if(ctl==1&&ctr==2)//如果第一个为左插头,第二个为右插头,则形成回路
					ans=max(ans,val+g[i][j]);
				if(ctl==2&&ctr==1)//如果第一个为右插头,第二个为左插头,则形成一条线段,不影响其他线段,消除两个插头转移 
					Insert(nxt,S^Get_s(2,j-1)^Get_s(1,j),val+g[i][j]);
				
			}
			f[now].clear();
			now^=1;
		}
		for(auto k:f[now])//当转移到下一行的时候要注意所有状态应该四进制右移一位,然后截去最高的那位四进制,原理靠图理解 
		{
			int S=k.first,val=k.second;
			f[now^1][(S<<2)&mxn]+=val;
		}
		f[now].clear();
		now^=1;
	}
}
bool Solve()
{
 	//freopen("test.in","r",stdin);
	n=Read(); m=Read();
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			g[i][j]=Read();		
	Ctdp();
	printf("%lld\n",ans);
	return true;
}
signed main()
{
	//T=Read();
	while(T--)
		if(!Solve())
			printf("-1\n");
	return 0;
}
/*
-std=c++11
-std=c99
*/


标签:ch,P3190,游乐园,int,HNOI2007,getchar,define
From: https://www.cnblogs.com/yexinqwq/p/17277012.html

相关文章

  • 【题解】[HNOI2007]梦幻岛宝珠
    题目分析:对于这种某一个值很大另一个值很小的背包题,就是要求找特殊性质。既然每一个\(w\)都可以写成\(a\times2^b\)的性质,就可以对于每一个\(b\)单独做背包,这样......
  • [HNOI2007]梦幻岛宝珠
    题意:01背包,但空间巨大。观察到每个 w_iwi​ 能写成 a*2^b (a,b∈N) 的形式,于是可以先把b相同的宝珠做一次合并,随后再进行总的合并。b相同的宝珠合并时直接可以使......
  • 游乐园智慧向导小程序设计与实现-计算机毕业设计源码+LW文档
                           小程序开发说明开发语言:Java框架:ssmJDK版本:JDK1.8服务器:tomcat7数据库:mysql5.7(一定要5.7版本)数据库工具:Navicat11开发软......
  • P3188 [HNOI2007]梦幻岛宝珠 题解
    一道不错的dp题,下令原背包容量为\(m\)。注意到\(w_i=a\times2^b\)中\(a,b\)都比较小,尝试按照\(a\)或者\(b\)分组然后合并,但是显然如果我们按照\(a\)分组就......
  • BZOJ 1185([HNOI2007]最小矩形覆盖-旋转卡壳+点集几何意义)
    1185:[HNOI2007]最小矩形覆盖TimeLimit: 10Sec  MemoryLimit: 162MBSec  SpecialJudgeSubmit: 258  Solved: 137Description l要事先改成......
  • BZOJ 1189([HNOI2007]紧急疏散evacuate-网络流二分+拆点)
    发生了火警,所有人员需要紧急疏散!假设每个房间是一个NM的矩形区域。每个格子如果是’.’,那么表示这是一块空地;如果是’X’,那么表示这是一面墙,如果是’D’,那么表示这是一扇门......
  • [HNOI2007]紧急疏散EVACUATE
    题目传送门:[HNOI2007]紧急疏散EVACUATEbfs+二分+最大流#include<queue>#include<string>#include<cstdio>#include<cstring>#include<algorithm>constintN=2......
  • 数位dp P3188 [HNOI2007]梦幻岛宝珠-Solution
    数位考虑+背包(+滚动数组)首先,我们能发现,这是一道\(n\)很小但是体积和权值都非常大的背包。但是这个题的体积有一个特殊的性质,就是他是\(a\times2^b,a\leq10\)的形......