【题目大意】
给出一个网格，经过边要付出代价。求走过每一个格子的欧拉回路的最小代价。
【思路】
裸裸的插头DP~然而写了好久orz
【错误点】
整个人跟制杖了一样QAQ
hash实力写挂…m和n搞反了。具体看注释。
#include<bits/stdc++.h>
#define u 0
#define d 1
#define l 2
#define r 3
using namespace std;
typedef long long ll;
const int MAXN=;
const int HASH=;
struct Hashmap
{
vector<int> hash[HASH];
vector<ll> state,f;
void clear()
{
for (int i=;i<HASH;i++) vector<int>().swap(hash[i]);
vector<ll>().swap(state);
vector<ll>().swap(f);
} void push(ll st,ll ans)
{
int now=st%HASH;
for (int i=;i<hash[now].size();i++)
{
int h=hash[now][i];
if (state[h]==st) //st写成了now QAQ下面return还忘记写到大括号里面去了，浪费了3个小时查orz
{
f[h]=min(f[h],ans);
return;
}
}
hash[now].push_back(state.size());
state.push_back(st);
f.push_back(ans);
}
}dp[];
int m,n;
int maze[MAXN][MAXN][],code[MAXN];//上下左右
int ch[MAXN]; void decode(ll st)
{
for (int i=n;i>=;i--)
{
code[i]=st&;
st>>=;
}
} ll encode()
{
ll ret=;
int cnt=;
memset(ch,-,sizeof(ch));
ch[]=;
for (int i=;i<=n;i++)
{
if (ch[code[i]]==-) ch[code[i]]=++cnt;
code[i]=ch[code[i]];
ret<<=;
ret+=code[i];
}
return ret;
} void shift()
{
for (int i=n;i>;i--) code[i]=code[i-];
code[]=;
} void dpblank(int i,int j,int cur)
{
for (int k=;k<dp[-cur].state.size();k++)
{
decode(dp[-cur].state[k]);
if (j==)
{
if (code[n]!=) continue;
else shift();
}
int left=code[j-],up=code[j];//left和up要等到shift之后再取值
if (left && up)
{
if (left==up)
{
if (i==m && j==n)
{
code[j-]=code[j]=;
dp[cur].push(encode(),dp[-cur].f[k]);
}
}
else
{
code[j-]=code[j]=;
for (int i=;i<=n;i++) if (code[i]==left) code[i]=up;
dp[cur].push(encode(),dp[-cur].f[k]);
}
} if ((left && !up) || (up && !left))
{
int t=left|up;
if (j<n)
{
code[j-]=,code[j]=t;
dp[cur].push(encode(),dp[-cur].f[k]+maze[i][j][r]);
}
if (i<m)
{
code[j-]=t,code[j]=;
dp[cur].push(encode(),dp[-cur].f[k]+maze[i][j][d]);
}
} if (!left && !up)
{
if (i<m && j<n)
{
code[j-]=code[j]=MAXN-;
dp[cur].push(encode(),dp[-cur].f[k]+maze[i][j][d]+maze[i][j][r]);
}
}
}
} void init()
{
scanf("%d%d",&m,&n);
char str[MAXN];
getchar();
gets(str);
memset(maze,0xef,sizeof(maze));
for (int i=;i<=m;i++)
{
gets(str);
for (int j=;j<=(n-);j++)
maze[i][j][r]=maze[i][j+][l]=str[*j]-'';
if (i!=m)
{
gets(str);
for (int j=;j<=n;j++)
maze[i][j][d]=maze[i+][j][u]=str[*j-]-'';
} }
gets(str);
}
void solve()
{
int cur=;
dp[cur].clear();
dp[cur].push(,);
for (int i=;i<=m;i++)
for (int j=;j<=n;j++)//m和n写反掉啦
{
cur^=;
dp[cur].clear();
dpblank(i,j,cur);
}
ll ans=1e16;
for (int i=;i<dp[cur].state.size();i++) ans=min(ans,dp[cur].f[i]);
printf("%lld\n",ans);
} int main()
{
int T;
scanf("%d",&T);
while (T--)
{
init();
solve();
}
return ;
}
[附赠:随机生成数据的程序，欢迎对拍~]
#include<bits/stdc++.h>
using namespace std; int main()
{
freopen("test.out","w",stdout);
cout<<<<endl;
for (int t=;t<=;t++)
{
int m=rand()%+,n=rand()%+;
cout<<m<<' '<<n<<endl;
for (int i=;i<=(*n+);i++) cout<<'#';cout<<endl;
for (int i=;i<=m;i++)
{
cout<<"# ";
for (int j=;j<n;j++)
{
int x=rand()%;
cout<<x<<' ';
}
cout<<"#"<<endl;
if (i==m) break;
cout<<'#';
for (int j=;j<=n;j++)
{
int x=rand()%;
cout<<x<<'#';
}
cout<<endl;
}
for (int i=;i<=(*n+);i++) cout<<'#';cout<<endl;
}
return ;
}