插頭DP一般都是棋盤模型，找路徑或者環(huán)路最值或者方案數(shù)。
插頭：說白了就是兩個(gè)聯(lián)通的格子，一個(gè)走向另一個(gè)，那么這里就有一個(gè)插頭。
輪廓線：DP逐格DP，那么輪廓線可以分開DP過的格子和未DP的格子。輪廓線的長(zhǎng)度明顯是m+1。插頭垂直于輪廓線。
轉(zhuǎn)移：
輪廓線在換行的時(shí)候要位移，這個(gè)畫畫圖就出來了。
然后具體問題具體討論。比如任意多個(gè)環(huán)路，不考慮方向，那么就是eat the trees，用最小表示法，因?yàn)槭侨我舛鄠€(gè)環(huán)路，那么插頭只有兩種，一種是有插頭，一種是沒插頭，具體聯(lián)通與否我們不管。如果要考慮方向呢？那么插頭就有3種，一種是沒插頭，一種是插頭從已DP的指向未DP的，一種是未DP的指向已DP的。
具體實(shí)現(xiàn)，有兩種思路，一種是括號(hào)序列，一種是最小表示法。
括號(hào)序列比較快，空間壓縮得很好，不過轉(zhuǎn)移太麻煩辣。
最小表示法轉(zhuǎn)移比較好想，就是比較慢，空間比較大。
寫法有三種，一種是hash表存取狀態(tài)，有decode，encode，就是kuangbin那種寫法；一種是傳統(tǒng)dp寫法，位運(yùn)算取出狀態(tài)；還有種是claris寫法，預(yù)處理所有可能狀態(tài)然后傳統(tǒng)DP轉(zhuǎn)移。
kuangbin那個(gè)因?yàn)槲贿\(yùn)算比較少，每次都會(huì)直接接觸到解密的狀態(tài)，比較直觀好想，模式化很強(qiáng)，不過每次都有O(m)的常數(shù)用在加密解密上。時(shí)空耗費(fèi)較大，要寫hash表，代碼較長(zhǎng)。
傳統(tǒng)DP轉(zhuǎn)移有的是O(1)，有的O(n)，總體來說和上面的差不多。。因?yàn)檫f推轉(zhuǎn)移無效狀態(tài)比較多。然后代碼比較短。缺點(diǎn)就是一堆位運(yùn)算像我這種傻逼根本看不懂
claris寫法太神辣。因?yàn)樗袪顟B(tài)預(yù)處理好了所以狀態(tài)數(shù)很少，因?yàn)轭A(yù)處理所以所有轉(zhuǎn)移O(1)，然后代碼很短。缺點(diǎn)是我這種傻逼不會(huì)預(yù)處理。然后還是一堆位運(yùn)算。并且遇到題目本身狀態(tài)很多的時(shí)候效果不會(huì)很好。
我現(xiàn)在只會(huì)第一種寫法。
下面扔2個(gè)例題。
HYSBZ 3125
找一條走過所有格子的環(huán)路的方案數(shù)。
有的格子只能上下經(jīng)過，有的只能左右經(jīng)過，有的不能經(jīng)過。
這個(gè)題我寫的括號(hào)序列。
插頭3種，空插頭，左括號(hào)，右括號(hào)。
然后分9類情況討論即可。
因?yàn)榉至?類情況所以代碼長(zhǎng)爆。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int HASH=10007,STATE=1000010,MAXD=15;
int n,m,ex,ey,code[MAXD];
char maze[MAXD][MAXD];
struct HASHMAP{
int head[HASH],next[STATE],state[STATE],size;
ll f[STATE];
void init()
{
size=0;
memset(head,-1,sizeof head);
}
void push(int st,ll val)
{
int h=st%HASH;
for(int i=head[h];i!=-1;i=next[i])
if(st==state[i])
{
f[i]+=val;
return;
}
f[size]=val;
state[size]=st;
next[size]=head[h];
head[h]=size++;
}
}hm[2];
int encode(int *code,int m)
{
int st=0;
for(int i=0;i<=m;i++)
{
st*=3;
st+=code[i];
}
return st;
}
void decode(int *code,int m,int st)
{
for(int i=m;i>=0;i--)
{
code[i]=st%3;
st/=3;
}
}
void shift(int *code,int m)
{
for(int i=m;i>0;--i)code[i]=code[i-1];
code[0]=0;
}
void dpblank(int i,int j,int cur)
{
for(int k=0;k<hm[cur].size;++k)
{
decode(code,m,hm[cur].state[k]);
int &p=code[j-1],&q=code[j];
if(!p&&!q)
{
if((maze[i+1][j]=='|'||maze[i+1][j]=='.')&&(maze[i][j+1]=='-'||maze[i][j+1]=='.'))
{
p=1,q=2;
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
}
else if(p&&q)
{
if(p==1&&q==1)
{
int tot=0;
for(int ii=j;ii<=m;++ii)
{
if(code[ii]==1)++tot;
if(code[ii]==2)--tot;
if(tot==0)
{
code[ii]=1;
break;
}
}
p=0,q=0;
if(j==m)shift(code,m);
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
else if(p==2&&q==2)
{
int tot=0;
for(int ii=j-1;ii>=0;--ii)
{
if(code[ii]==2)++tot;
if(code[ii]==1)--tot;
if(tot==0)
{
code[ii]=2;
break;
}
}
p=0,q=0;
if(j==m)shift(code,m);
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
else if(p==1&&q==2)
{
if(i==ex&&j==ey)
{
p=0,q=0;
if(j==m)shift(code,m);
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
}
else if(p==2&&q==1)
{
p=0,q=0;
if(j==m)shift(code,m);
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
}
else
{
if(maze[i][j+1]=='.'||maze[i][j+1]=='-')
{
q=p+q,p=0;
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
if(maze[i+1][j]=='.'||maze[i+1][j]=='|')
{
p=p+q,q=0;
if(j==m)shift(code,m);
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
}
}
}
void dpver(int i,int j,int cur)
{
for(int k=0;k<hm[cur].size;++k)
{
decode(code,m,hm[cur].state[k]);
int &p=code[j-1],&q=code[j];
if(p==0&&q)
{
if(maze[i+1][j]=='.'||maze[i+1][j]=='|')
{
p=q,q=0;
if(j==m)shift(code,m);
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
}
}
}
void dphor(int i,int j,int cur)
{
for(int k=0;k<hm[cur].size;++k)
{
decode(code,m,hm[cur].state[k]);
int &p=code[j-1],&q=code[j];
if(p&&q==0)
{
if(maze[i][j+1]=='.'||maze[i][j+1]=='-')
{
q=p,p=0;
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
}
}
}
void dpblock(int i,int j,int cur)
{
for(int k=0;k<hm[cur].size;++k)
{
decode(code,m,hm[cur].state[k]);
code[j-1]=0,code[j]=0;
if(j==m)shift(code,m);
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%s",maze[i]+1);
for(int j=1;j<=m;++j)
if(maze[i][j]=='.')ex=i,ey=j;
}
int cur=0;
ll ans=0;
hm[cur].init();
hm[cur].push(0,1);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
hm[cur^1].init();
if(maze[i][j]=='.')dpblank(i,j,cur);
else if(maze[i][j]=='|')dpver(i,j,cur);
else if(maze[i][j]=='-')dphor(i,j,cur);
else dpblock(i,j,cur);
cur^=1;
}
for(int i=0;i<hm[cur].size;++i)ans+=hm[cur].f[i];
printf("%lld\n",ans);
}

Jetbrains全家桶1年46，售后保障穩(wěn)定

bzoj2310 parkii
這個(gè)題就是弱化的zoj3213
棋盤上的格子有權(quán)值。找一條路徑使路徑上的權(quán)值之和最大。
這題我用的最小表示法，需要因?yàn)檫@個(gè)是路徑不是回路，需要增加獨(dú)立插頭，同事需要增加標(biāo)志位記錄獨(dú)立插頭個(gè)數(shù)。要使獨(dú)立插頭個(gè)數(shù)小于等于2.具體實(shí)現(xiàn)的時(shí)候把標(biāo)志位也壓進(jìn)狀態(tài)里面。
最小表示法就相對(duì)好討論一些。因?yàn)槔ㄌ?hào)序列的性質(zhì)，輪廓線上m+1個(gè)點(diǎn)最多只有m/2個(gè)不同的聯(lián)通塊，根據(jù)這個(gè)壓位DP。
如果左插頭和上插頭都有，那么右插頭和下插頭就沒有了。有以下2種情況：
1、如果左插頭和上插頭都有且不在一個(gè)聯(lián)通塊內(nèi)，就連接他們。連接還要重標(biāo)號(hào)最小表示。因?yàn)橐郧白蟛孱^所在聯(lián)通塊和上插頭所在聯(lián)通塊不是一個(gè)，現(xiàn)在要暴力修改。
2、如果左插頭和上插頭都有且在一個(gè)聯(lián)通塊內(nèi)，就不管了。
如果左插頭和上插頭只有一個(gè)，那么就有以下3種情況：
1、這個(gè)插頭可以延續(xù)一個(gè)右插頭
2、這個(gè)插頭可以延續(xù)一個(gè)下插頭
3、這個(gè)插頭可以延續(xù)一個(gè)獨(dú)立插頭
注意延續(xù)一個(gè)右/下插頭不要走出棋盤了，注意延續(xù)獨(dú)立插頭的前提是輪廓線上獨(dú)立插頭數(shù)量小于2
如果左插頭和上插頭都沒有，那么就有以下3種情況：
1、右插頭和下插頭都得有，現(xiàn)在他們倆在一個(gè)聯(lián)通塊內(nèi)。注意這樣不要走出棋盤了。
2、左插頭變成獨(dú)立插頭再延續(xù)一個(gè)右插頭。注意延續(xù)獨(dú)立插頭的前提是輪廓線上獨(dú)立插頭數(shù)量小于2。
3、右插頭變成獨(dú)立插頭再延續(xù)一個(gè)左插頭。注意延續(xù)獨(dú)立插頭的前提是輪廓線上獨(dú)立插頭數(shù)量小于2。
這樣就討論完了。注意換行的時(shí)候狀態(tài)要位移。如果用括號(hào)序列分類有16種= =這個(gè)我太傻逼了不會(huì)做。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int HASH=10007,STATE=1000010,MAXD=15;
int n,m,num,code[MAXD],ch[MAXD],maze[105][MAXD];
struct HASHMAP{
int head[HASH],next[STATE],state[STATE],f[STATE],size;
void init()
{
size=0;
memset(head,-1,sizeof head);
}
void push(int st,int val)
{
int h=st%HASH;
for(int i=head[h];~i;i=next[i])
if(st==state[i])
{
f[i]=max(f[i],val);
return;
}
f[size]=val;
state[size]=st;
next[size]=head[h];
head[h]=size++;
}
}hm[2];
int encode(int *code,int m)
{
int st=0,cnt=1;
memset(ch,-1,sizeof ch);
ch[0]=0;
for(int i=0;i<=m;++i)
{
if(ch
]==-1)ch
]=cnt++;
code[i]=ch
];
st<<=3;
st|=code[i];
}
st<<=3;
st|=num;
return st;
}
void decode(int *code,int m,int st)
{
num=st&7;
st>>=3;
for(int i=m;i>=0;--i)
{
code[i]=st&7;
st>>=3;
}
}
void dp(int i,int j,int cur)
{
for(int k=0;k<hm[cur].size;++k)
{
decode(code,m,hm[cur].state[k]);
int p=code[j-1],q=code[j];
if(p&&q)
{
if(p!=q)
{
for(int ii=0;ii<=m;++ii)
if(code[ii]==q)code[ii]=p;
code[j-1]=code[j]=0;
hm[cur^1].push(encode(code,j==m?m-1:m),hm[cur].f[k]+maze[i][j]);
}
}
else if(p||q)
{
if(j+1<=m)
{
code[j]=p+q,code[j-1]=0;
hm[cur^1].push(encode(code,m),hm[cur].f[k]+maze[i][j]);
}
if(i+1<=n)
{
code[j-1]=p+q,code[j]=0;
hm[cur^1].push(encode(code,j==m?m-1:m),hm[cur].f[k]+maze[i][j]);
}
if(num<2)
{
++num;
code[j-1]=code[j]=0;
hm[cur^1].push(encode(code,j==m?m-1:m),hm[cur].f[k]+maze[i][j]);
}
}
else
{
code[j-1]=code[j]=0;
hm[cur^1].push(encode(code,j==m?m-1:m),hm[cur].f[k]);
if(j+1<=m&&i+1<=n)
{
code[j-1]=code[j]=13;
hm[cur^1].push(encode(code,m),hm[cur].f[k]+maze[i][j]);
}
if(num<2)
{
++num;
if(j+1<=m)
{
code[j-1]=0,code[j]=13;
hm[cur^1].push(encode(code,m),hm[cur].f[k]+maze[i][j]);
}
if(i+1<=n)
{
code[j-1]=13,code[j]=0;
hm[cur^1].push(encode(code,j==m?m-1:m),hm[cur].f[k]+maze[i][j]);
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
scanf("%d",&maze[i][j]);
int cur=0,ans=-999999999;
hm[cur].init();
hm[cur].push(0,0);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
ans=max(ans,maze[i][j]);
hm[cur^1].init();
dp(i,j,cur);
cur^=1;
}
for(int i=0;i<hm[cur].size;++i)ans=max(ans,hm[cur].f[i]);
printf("%d\n",ans);
}

總結(jié)

以上是生活随笔為你收集整理的插头DP小结_dp插头接线标准的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。