用\(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
*/