傳送門
題意簡述:給一個n*m的帶權矩陣,求從左上角走到右下角的最大分數,每個格子隻能經過最多一次, n , m ≤ 9 n,m\le9 n,m≤9。
思路:
考慮輪廓線 d p dp dp,但這道題并沒有出現回路的限制是以需要一點巧妙地轉化。
我們在加入初始值時規定第一個位置可以來一個插頭,然後最後統計到最後一個點的時候特判有沒有多餘的插頭即可。
注意在轉移過程中如果有連上兩個插頭剛好會産生回路的狀态要舍棄掉。
代碼:
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans*w;
}
const int mod=1e6+7;
struct Hash{
int mx[mod],idx[mod],tot,sta[mod];
inline void clear(){tot=0,memset(idx,-1,sizeof(idx));}
inline void insert(int stat,int mxn){
int pos=stat%mod;
if(!pos)++pos;
while(~idx[pos]&&sta[idx[pos]]!=stat)pos=pos==mod-1?1:pos+1;
if(~idx[pos])mx[idx[pos]]=max(mx[idx[pos]],mxn);
else mx[idx[pos]=++tot]=mxn,sta[tot]=stat;
}
}f[2];
int ans,n,m,a[15][15],Cas=0;
bool cur,mp[15][15];
inline int getbit(int x,int p){return (x>>((p-1)<<1))&3;}
inline void update(int&x,int p,int v){x^=(getbit(x,p)^v)<<((p-1)<<1);}
inline void solve(){
f[cur=0].clear(),f[cur].insert(1,0),ans=-1e9;
for(ri i=1;i<=n;++i){
for(ri j=1;j<=m;++j){
f[(cur^=1)].clear();
for(ri mx,stat,p,q,tt=1;tt<=f[cur^1].tot;++tt){
stat=f[cur^1].sta[tt],p=getbit(stat,j),q=getbit(stat,j+1),mx=f[cur^1].mx[tt];
if(p==1&&q==2)continue;
if(!(p+q)){
f[cur].insert(stat,mx);
if(mp[i][j+1]&&mp[i+1][j])update(stat,j,1),update(stat,j+1,2),f[cur].insert(stat,mx+a[i][j]);
continue;
}
if((p>0)^(q>0)){
if(i==n&&j==m){
update(stat,j,0),update(stat,j+1,0);
if(!stat)ans=max(ans,mx+a[i][j]);
continue;
}
if(mp[i+(p>0)][j+(q>0)])f[cur].insert(stat,mx+a[i][j]);
if(mp[i+(q>0)][j+(p>0)])update(stat,j,q),update(stat,j+1,p),f[cur].insert(stat,mx+a[i][j]);
continue;
}
update(stat,j,0),update(stat,j+1,0);
if(p==2&&q==1){f[cur].insert(stat,mx+a[i][j]);continue;}
if(p==1){
for(ri cnt=1,k=j+2,bit;k<=m+1;++k){
bit=getbit(stat,k);
if(bit==1)++cnt;
if(bit==2)--cnt;
if(!cnt){update(stat,k,1),f[cur].insert(stat,mx+a[i][j]);break;}
}
continue;
}
for(ri cnt=-1,k=j-1,bit;k;--k){
bit=getbit(stat,k);
if(bit==1)++cnt;
if(bit==2)--cnt;
if(!cnt){update(stat,k,2),f[cur].insert(stat,mx+a[i][j]);break;}
}
}
}
for(ri j=1;j<=f[cur].tot;++j)f[cur].sta[j]<<=2;
}
}
int main(){
while(~scanf("%d%d",&n,&m)){
++Cas,memset(mp,0,sizeof(mp)),memset(a,0,sizeof(a));
for(ri i=1;i<=n;++i)for(ri j=1;j<=m;++j)a[i][j]=read(),mp[i][j]=1;
solve(),cout<<"Case "<<Cas<<": "<<ans<<'\n';
}
return 0;
}