[HNOI2007]神奇游乐园
最近有一点说话不过大脑的感觉,注意一下吧。
description
\(n*m\)的网格图,每个格子有权值,问最大至少含四个格子的欧拉回路路径和。
solution
插头dp。
注意:
1.!p,!q时,可以不放,该位状态为0,但也算一种状态。
2.要判边界(不然会错)
3.统计前答案前,要判断除了p=1,q=2两位其余位要全部为0。
code
点击查看代码
#include
using namespace std;
const int N=105;
const int M=7;
const int mod=40001;
const int inf=1e9;
int val[N][M],n,m,pre,now,state[2][mod],dp[2][mod],tot[2];
struct hash {
int head[mod],nxt[mod];
void Insert(int S,int num) {
int x=S%mod;
for(int i=head[x];~i;i=nxt[i]) {
if(state[now][i]==S) {dp[now][i]=max(dp[now][i],num);return;}
}
int t(tot[now]);
dp[now][t]=num;state[now][t]=S;nxt[t]=head[x];head[x]=tot[now]++;
}
void Clear() {
memset(head,-1,sizeof(head));tot[now]=0;
}
}H;
bool mp[N][M];
int _get(int S,int p) {
return (S>>(2*p))&3;
}
void _set(int &S,int p,int v) {
S^=_get(S,p)<<(p*2);
S|=v<<(p*2);
}
void DP() {
int ans=-inf;
pre=0,now=1;
dp[now][0]=0;state[now][tot[now]++]=0;
for(int i=0;i0)^(q>0)) {
if(mp[i+(p>0)][j+(q>0)])H.Insert(S,num);
if(mp[i+(q>0)][j+(p>0)]) {int nS=S;_set(nS,j,q),_set(nS,j+1,p);H.Insert(nS,num);}
}
else if(p==1&&q==1) {
int sum=1;
for(int v=j+2;v<=m;v++) {
int k=_get(S,v);
if(k)sum+=(k==2)?-1:1;
if(!sum) {
int nS=S;_set(nS,j,0),_set(nS,j+1,0),_set(nS,v,1);
H.Insert(nS,num);
break;
}
}
}
else if(p==2&&q==2) {
int sum=1;
for(int v=j-1;v>=0;v--) {
int k=_get(S,v);
if(k)sum+=(k==1)?-1:1;
if(!sum) {
int nS=S;_set(nS,j,0),_set(nS,j+1,0),_set(nS,v,2);
H.Insert(nS,num);
break;
}
}
}
else if(p==2&&q==1) {
int nS=S;_set(nS,j,0),_set(nS,j+1,0);
H.Insert(nS,num);
}
else if(p==1&&q==2) {
int nS=S;_set(nS,j,0),_set(nS,j+1,0);
if(!nS)ans=max(ans,num);
}
}
}
for(int j=0;j