[专题总结]初探插头dp
2024-09-01 22:02:50
彻彻底底写到自闭的一个专题。
就是大型分类讨论，压行+宏定义很有优势。
常用滚动数组+哈希表+位运算。当然还有轮廓线。
Formula 1：
经过所有格子的哈密顿回路数。
每个非障碍点必须有且仅有2个插头（含上下左右）。
若左上都没有，那么新建两个插头1和2。
若左上只有一个插头，那么它就向右下方向之一延伸。
若左上都有，那么不建新插头。
如果是左1上2，那么就是形成了一条回路，当且仅当在全图右下角更新答案。
如果都是1，那么就要把右边的两个2改成一对插头，就是把靠右的一个1插头匹配的2插头改为1。
都是2同理。
如果是左2上1，那么就是链接了两个路径，两个插头抵消。
#include<cstdio>
#define cri const register int
int bl[][],n,m,now,last=,ln,lm,fn,fm,r[]={,,-};long long ans;
int read(){
register char ch=getchar();
while(ch!='*'&&ch!='.')ch=getchar();
return ch=='*';
}
struct hash{
int fir[],l[],to[],cnt;long long v[];
void clear(){
for(int i=;i<;++i)to[i]=-,fir[i]=v[i]=;cnt=;
}
long long &operator[](cri pos){
int i;
for(i=fir[pos%];i&&to[i]!=pos;i=l[i]);
if(!i)l[++cnt]=fir[pos%],to[cnt]=pos,fir[pos%]=i=cnt;
return v[i];
}
}f[];
inline int find(cri st,cri p){return st>>(p-<<)&;}
inline void set(int &st,cri p,cri k){st&=~(<<(p-<<));st|=k<<(p-<<);}
inline int get(cri st,cri p){
int dirc=(find(st,p)==)?:-;
for(int i=p,pl=find(st,i),cnt=r[pl];i&&i<=m+;pl=find(st,i+=dirc),cnt+=r[pl])
if(cnt==)return i;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i)for(int j=;j<=m;++j){
bl[i][j]=read();
if(!bl[i][j])ln=i,lm=j;
if(!fn&&!bl[i][j])fn=i,fm=j;
}f[][]=;
for(int i=;i<=n;++i)bl[i][m+]=;
for(int i=;i<=m;++i)bl[n+][i]=;
for(int i=fn;i<=n;++i){
for(int j=(i==fn)?fm:;j<=m;++j){
last^=;now^=; f[now].clear();
for(int k=;k<=f[last].cnt;++k){
int st=f[last].to[k],p1=find(st,j),p2=find(st,j+);
long long v=f[last].v[k];//printf("%d %d %d %d %d %lld\n",i,j,st,p1,p2,v);
if(bl[i][j]&&(p1||p2))continue;
if(bl[i][j])f[now][st]+=v;
else if(!p1&&!p2){if(!bl[i][j+]&&!bl[i+][j])set(st,j,),set(st,j+,),f[now][st]+=v;}
else if(p1&&!p2){
if(!bl[i+][j])f[now][st]+=v;//,printf("---%d %d %lld %lld\n",i,j,v,f[now][st]);
if(!bl[i][j+])set(st,j+,p1),set(st,j,),f[now][st]+=v;
}
else if(!p1&&p2){
if(!bl[i][j+])f[now][st]+=v;
if(!bl[i+][j])set(st,j,p2),set(st,j+,),f[now][st]+=v;
}
else if(p1==&&p2==){if(i==ln&&j==lm)ans+=v;}
else if(p2==&&p1==)set(st,j,),set(st,j+,),f[now][st]+=v;
else if(p1==&&p2==)set(st,get(st,j+),),set(st,j,),set(st,j+,),f[now][st]+=v;
else if(p1==&&p2==)set(st,get(st,j),),set(st,j,),set(st,j+,),f[now][st]+=v;
}
}
for(int i=;i<=f[now].cnt;++i)f[now].to[i]<<=;
}
printf("%lld\n",ans);
}
当时我还不会压行
CITY
和上面同理，只不过限制了插头方向。
#include<cstdio>
#define int long long
#define mod 54321
int n,m,bl[][],ref[],fn,fm,ln,lm,last=,now,tf[]={,,-};long long ans;
int read(){
register char ch=getchar();
while(ch!='.'&&ch!='#'&&ch!='-'&&ch!='|')ch=getchar();
return ref[ch];
}
struct hash{
int fir[mod],l[mod],to[mod],cnt;long long v[mod];
void clear(){for(int i=;i<mod;++i)fir[i]=v[i]=,to[i]=-;cnt=;}
long long &operator[](int p){
int i;
for(i=fir[p%mod];i&&to[i]!=p;i=l[i]);
if(!i)l[++cnt]=fir[p%mod],fir[p%mod]=i=cnt,to[cnt]=p;
return v[i];
}
}f[];
int find(int st,int p){return st>>(p-<<)&;}
void set(int &st,int p,int k){st&=~(<<(p-<<));st|=k<<(p-<<);}
void reset(int &st,int p){
for(int i=p,pl=find(st,i),di=tf[find(st,p)],cnt=di;i&&i<=m+;i+=di,pl=find(st,i),cnt+=tf[pl])
if(!cnt){set(st,i,pl==?:);return;}
}
main(){
scanf("%lld%lld",&n,&m);ref['#']=;ref['-']=;ref['|']=;
for(int i=;i<=n;++i)for(int j=;j<=m;++j){
bl[i][j]=read();
if(!bl[i][j])ln=i,lm=j;
if(!bl[i][j]&&!fn)fn=i,fm=j;
}
f[][]=;
for(int i=;i<=n;++i)bl[i][m+]=;
for(int i=;i<=m;++i)bl[n+][i]=;
for(int i=fn;i<=n;++i){
for(int j=(i==fn?fm:);j<=m;++j){
last^=;now^=;f[now].clear();
for(int k=;k<=f[last].cnt;++k){
int st=f[last].to[k],p1=find(st,j),p2=find(st,j+);long long v=f[last].v[k];//printf("%d %d %d %d %d %lld\n",i,j,st,p1,p2,v);
if(((bl[i][j]&)&&p2)||((bl[i][j]&)&&p1))continue;
if(bl[i][j]==){if(!p1&&!p2)f[now][st]+=v;continue;}
if(bl[i][j]==){if((!(bl[i+][j]&))&&p2&&!p1)set(st,j+,),set(st,j,p2),f[now][st]+=v;continue;}
if(bl[i][j]==){if((!(bl[i][j+]&))&&p1&&!p2)set(st,j,),set(st,j+,p1),f[now][st]+=v;continue;}
if(!p1&&!p2){if(!(bl[i][j+]&)&&!(bl[i+][j]&))set(st,j,),set(st,j+,),f[now][st]+=v;}
else if(p1&&!p2){
if(!(bl[i+][j]&))f[now][st]+=v;
if(!(bl[i][j+]&))set(st,j,),set(st,j+,p1),f[now][st]+=v;
}
else if(p2&&!p1){
if(!(bl[i][j+]&))f[now][st]+=v;
if(!(bl[i+][j]&))set(st,j+,),set(st,j,p2),f[now][st]+=v;
}
else if(p1==&&p2==){if(i==ln&&j==lm)ans+=v;}
else if(p2==&&p1==)set(st,j,),set(st,j+,),f[now][st]+=v;
else if(p1==&&p2==)reset(st,j+),set(st,j,),set(st,j+,),f[now][st]+=v;
else if(p1==&&p2==)reset(st,j),set(st,j,),set(st,j+,),f[now][st]+=v;
}
}
for(int j=;j<=f[now].cnt;++j)f[now].to[j]<<=;
}
printf("%lld\n",ans);
}
我依旧不会压行
邮递员
依旧同理。注意n或m=1。
#include<cstdio>
#define hash_mod 54321
#define int_mod 100000000000000ll
#define cri const register int
int n,m;
struct gj{
long long x[];
inline void clear(){x[]=x[]=x[]=x[]=x[]=;}
inline void print(){
int i;
for(i=;i>=;--i)if(x[i]){printf("%lld",x[i]);break;}
for(i--;i>=;--i)printf("%014lld",x[i]);puts("");
}
inline void operator+=(const gj &b){
for(int i=;i>=;--i)x[i]+=b.x[i];
for(int i=;i<=;++i)x[i+]+=x[i]/int_mod,x[i]%=int_mod;
}
}ans;
struct hash_map{
int fir[],l[],to[],cnt;gj v[];
void clear(){
for(int i=;i<;++i)fir[i]=,v[i].clear(),to[i]=-;
cnt=;
}
gj &operator[](const int key){
int pos=key%hash_mod,i;
for(i=fir[pos];to[i]!=key&&i;i=l[i]);
if(!i)to[++cnt]=key,l[cnt]=fir[pos],i=fir[pos]=cnt,v[cnt].clear();
return v[i];
}
}hash[];
inline int find(cri st,cri pos){return st>>(pos-<<)&;}
inline int get(cri st,cri pos){
int cnt=,dirc=(find(st,pos)==)?:-;
for(int i=pos,plug=find(st,pos);i&&i<=m+;plug=find(st,i+=dirc)){
if(plug==)cnt++;else if(plug==)cnt--;
if(cnt==)return i;
}
return -;
}
inline void set(int &st,cri pos,cri kind){
st|=<<(pos-<<);st^=<<(pos-<<);
st|=kind<<(pos-<<);
}
void DP(cri x,cri y){
int now=(x-)*m+y&,last=now^,tot=hash[last].cnt;
hash[now].clear();
for(int i=;i<=tot;++i){
int st=hash[last].to[i],plug1=find(st,y),plug2=find(st,y+);
gj v=hash[last].v[i];//printf("%d %d %d %d %d ",x,y,st,plug1,plug2);v.print();
if(get(st,y)==-||get(st,y+)==-)continue;
if(!plug1&&!plug2){if(y!=m&&x!=n)set(st,y,),set(st,y+,),hash[now][st]+=v;}
else if(plug1&&!plug2){
if(x!=n)hash[now][st]+=v;
if(y!=m)set(st,y,),set(st,y+,plug1),hash[now][st]+=v;
}
else if(!plug1&&plug2){
if(y!=m)hash[now][st]+=v;
if(x!=n)set(st,y,plug2),set(st,y+,),hash[now][st]+=v;
}
else if(plug1==&&plug2==){if(x==n&&y==m)ans+=v;}
else if(plug1==&&plug2==)set(st,y,),set(st,y+,),hash[now][st]+=v;
else if(plug1==&&plug2==)
set(st,get(st,y+),),set(st,y,),set(st,y+,),hash[now][st]+=v;
else if(plug1==&&plug2==)
set(st,get(st,y),),set(st,y,),set(st,y+,),hash[now][st]+=v;
}//printf("%d--%d--%d\n",x,y,hash[now].cnt);
}
int main(){
scanf("%d%d",&n,&m);
hash[].clear();hash[][].x[]=;
if(n==||m==){printf("");return ;}
if(n<m)n^=m,m^=n,n^=m;
for(int i=;i<=n;++i){
for(int j=;j<=m;++j)DP(i,j);
if(i!=n){
int now=(i*m)&,tot=hash[now].cnt;
for(int i=;i<=tot;++i)hash[now].to[i]<<=;
}
}
if(ans.x[]==){puts("");return ;}
ans+=ans;ans.print();
}
我还是不会压行
地板
这个插头不太一样。
对于一个L型，其实只有转弯前和转弯后两种状态。分别做1，2。
空格的话，可以把这个点作为拐角，往右下两个方向延伸出两个已经拐弯的插头。
如果只有一个1插头，那么可以选择转弯与否。
如果两个1插头碰在一起，那么它们就在这里转弯，互相抵消。
如果只有一个2插头，那么就延伸就好了。
#include<cstdio>
#include<cstring>
using namespace std;
#define mod 20110520
#define ad(a,b) add(dp[nx][set(set(st,j,a),j+1,b)],v)
void add(int &a,int b){a+=b;if(a>mod)a-=mod;}
int n,m,dp[][];char s[][];bool a[][];
int find(int st,int num){return st>>num*-&;}
int set(int st,int num,int v){return st^st&<<num*-^v<<num*-;}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i)scanf("%s",s[i]+);
if(n<m){
for(int i=;i<=n;++i)for(int j=;j<=m;++j)a[j][i]=s[i][j]=='_';
n^=m^=n^=m;
}else for(int i=;i<=n;++i)for(int j=;j<=m;++j)a[i][j]=s[i][j]=='_';
int nw=,nx=;dp[][]=;
for(int i=;i<=n;++i){
for(int j=;j<=m;++j){
nw^=;nx^=;
for(int st=;st<<<m*+;++st)if(dp[nw][st]){
int l=find(st,j),u=find(st,j+),v=dp[nw][st];dp[nw][st]=;
if(!a[i][j]){if(l==&&u==)ad(,);continue;}
if(l==&&u==)ad(,),ad(,),ad(,);
else if(l==&&u==)ad(,),ad(,);
else if(l==&&u==)ad(,),ad(,);
else if(l==&&u==)ad(,);
else if(l==&&u==)ad(,),ad(,);
else if(l==&&u==)ad(,),ad(,);
}
}
nw^=;nx^=;
for(int st=;st<<<m*;++st)dp[nx][st<<]=dp[nw][st];
for(int st=;st<<<m*+;++st)dp[nw][st]=;
}printf("%d\n",dp[nx][]);
}
然后我开始压行
标识设计
题意补充：笔画的宽度一定是1，棋盘不用占满，L型不能旋转。
因为不能旋转，所以只有一种插头。
但是不能占满，这个好说，只不过多了一种如果这个格子是空格的话也可以不增加新插头。
然后就退化一下上一题的代码，不过区分一下已经写了几个L就行。
#include<cstdio>
#include<cstring>
using namespace std;
int dp[][],n,m,w[][],stc,cts[],ans=-,nw,nx=;
int find(int st,int num){return st>>num*&;}
void sch(int al,int st){if(al==m+)cts[++stc]=st;else for(int i=;i<=;++i)sch(al+,st|i<<al*);}
int set(int st,int num,int v){return st^st&<<num*^v<<num*;}
void maxi(int &a,int b){if(a<b)a=b;}
int rmat(int st,int p){for(int i=p+;;++i)if(find(st,i)==)return st-(<<i*);}
int lmat(int st,int p){for(int i=p-;;--i)if(find(st,i)==)return st+(<<i*);}
#define upd(a,b) maxi(dp[nx][set(set(st,j-1,a),j,b)],v)
int main(){
scanf("%d%d",&n,&m);memset(dp,0xa0,sizeof dp);
for(int i=;i<=n;++i)for(int j=;j<=m;++j)scanf("%d",&w[i][j]);
dp[nx][]=;sch(,);
for(int i=;i<=n;++i){
for(int j=;j<=m;++j){
nw^=;nx^=;memset(dp[nx],0xa0,sizeof dp[nx]);
for(int p=,st;p<=stc;++p)if(dp[nw][st=cts[p]]>=-){
int p1=find(st,j-),p2=find(st,j),v=dp[nw][st]+w[i][j];
if(p1==&&p2==)upd(,),maxi(dp[nx][st],dp[nw][st]);
if(p1==&&p2==)if(set(set(st,j-,),j,)==)maxi(ans,v);
if(p1==&&p2==)upd(,);
if((p1^p2)==)upd(,),upd(,);
if((p1^p2)==)upd(,),upd(,);
if(p1==&&p2==)maxi(dp[nx][rmat(set(set(st,j-,),j,),j)],v);
if(p1==&&p2==)maxi(dp[nx][lmat(set(set(st,j-,),j,),j)],v);
}
}
nw^=;nx^=;memset(dp[nx],0xa0,sizeof dp[nx]);
for(int p=,st;p<=stc;++p)if(cts[p]<<<m<<m)dp[nx][cts[p]<<]=dp[nw][cts[p]];
}printf("%d\n",ans);
}
压行越发熟练
Park II
毒瘤界的巅峰。
理论上有3个插头，16种情况，但是情况很多重复，所以可以压成9类。
因为这一题是路径而不是回路，而且也不用占满。
为了处理路径的问题，需要引进一种新的插头，就是一端为路径的端点，另一端在轮廓线上的插头，学习LadyLex称之为独立插头3。
所有插头合并情况如下：
1，两个空格：这个格子可以不放，也可以作为拐角放一对12插头，也可以作为路径端点在右下方向之一放一个3插头。
2，两个1/2：与回路的题做法一致。
3，两个3：如果没有其它插头，那么你已经让两个自由端联通了，如果不存在其它插头，那么就可以更新答案。
4，左1上2：在回路题里这样会形成回路，但是路径题不允许回路，所以不做操作。（也就是在代码里不用写出来这种情况）
5，左2上1：与回路的题做法一致。
6，只有一个插头：另一个可以向右下方向之一转弯。
7，只有一个3插头：它可以结束了，作为路径端点，这样的话如果没有其它插头就可以更新答案了。
8，只有一个1/2插头：它可以结束了，作为路径端点，这样的话与1/2配对的2/1插头应该变成孤立的3插头。
9，有一个1/2插头，另一个是3插头：它们匹配了，这样的话与1/2配对的2/1插头应该变成孤立的3插头。
没有其它情况了。
如果宏定义+压行足够优秀，这道题不一定会比前面的题长。
#include<cstdio>
#include<cstring>
using namespace std;
void maxi(int &a,int b){if(a<b)a=b;}
int set(int st,int p,int v){return st^st&<<p*^v<<p*;}
int get(int st,int p){return st>>p*&;}
int mat(int st,int p,int v,int d,int g,int c=){
for(;;p+=d)if(get(st,p)==g+){c--;if(!c)return st+(v-g-<<p*);}
else if(get(st,p)==(g^)+)c++;
}
int dp[][],w,n,m,nx,nw=,ans,c[],ac[];
#define up(a,b) maxi(dp[nx][set(set(st,j-1,a),j,b)],v)
#define cl set(set(st,j-1,0),j,0)
int main(){
scanf("%d%d",&n,&m);
memset(dp,0xa0,sizeof dp);dp[nx][]=;
for(int i=;i<=n;++i){
for(int j=;j<=m;++j){
nw^=;nx^=;memset(dp[nx],0xa0,sizeof dp[nx]);scanf("%d",&w);
for(int st=;st<<<m*+;++st)if(dp[nw][st]>-){
int p1=get(st,j-),p2=get(st,j),v=dp[nw][st]+w;
for(int q=;q<;++q)c[q]=;c[p1]++;c[p2]++;
if(c[]==)up(,),up(,),up(,),maxi(dp[nx][st],v-w);
if(c[]==)maxi(dp[nx][mat(cl,j,,,)],v);
if(c[]==)maxi(dp[nx][mat(cl,j,,-,)],v);
if(c[]==)if(!cl)maxi(ans,v);
if(p1==&p2==)up(,);
if(c[]==)up(p1|p2,),up(,p1|p2);
if(c[]&c[])if(!cl)maxi(ans,v);
if(c[]&(c[]|c[]))maxi(dp[nx][mat(cl,j,,,)],v);
if(c[]&(c[]|c[]))maxi(dp[nx][mat(cl,j,,-,)],v);
}
}
nx^=;nw^=;memset(dp[nx],0xa0,sizeof dp[nx]);
for(int st=;st<<<m*;++st)dp[nx][st<<]=dp[nw][st];
}printf("%d\n",ans);
}
毒瘤巅峰的压行巅峰
游览计划
插头dp的话不是很好做，开5种插头记录联通块就行了。
我没有这么写，我写的是最小斯坦纳树。
好像没听过很高端？实际上就是dp。
dp[i][j][st]表式包含(i,j)这个点的一个联通块所覆盖的景点集合为st（状态压缩）。
考虑转移：
首先如果(i,j)就是景点，编号为k，那么dp[i][j][k]=0;
这个点往四周扩展：dp[x][y][st]=min(dp[i][j][st]+w[x][y])
这个点的子集合并：dp[i][j][st]=min(dp[i][j][s1]+dp[i][j][s2]-w[i][j])，其中s1与s2的并集为st。
没了。
但是第一个转移出环了。用原来B组题里的那个SPFA解决循环dp就好了。
记录转移点回溯输出方案。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int xx[]={,,,-},yy[]={,-,,};
#define tx x+xx[i]
#define ty y+yy[i]
int w[][],n,m,k=,dp[][][],pre[][][],qx[],qy[],iq[][],v[][];
void SPFA(int st,int t=){
for(int i=;i<=n;++i)for(int j=;j<=m;++j)if(dp[i][j][st]<)qx[++t]=i,qy[t]=j,iq[i][j]=;
for(int h=,x,y;x=qx[h],y=qy[h],iq[x][y]=,h<=t;++h)for(int i=;i<;++i)
if(tx&&ty&&tx<=n&&ty<=m&&dp[tx][ty][st]>dp[x][y][st]+w[tx][ty]){
dp[tx][ty][st]=dp[x][y][st]+w[tx][ty];pre[tx][ty][st]=x<<|y<<|st;
if(!iq[tx][ty])iq[qx[++t]=tx][qy[t]=ty]=;
}
}
void dfs(int x,int y,int st){
v[x][y]=;int px=pre[x][y][st]>>,py=pre[x][y][st]>>&,pst=pre[x][y][st]&;
if(!pre[x][y][st])return;
dfs(px,py,pst);if(x==px&&y==py)dfs(px,py,st^pst);
}
int main(){
scanf("%d%d",&n,&m);memset(dp,0x3f,sizeof dp);
for(int i=;i<=n;++i)for(int j=;j<=m;++j)scanf("%d",&w[i][j]);
for(int i=;i<=n;++i)for(int j=;j<=m;++j)if(!w[i][j])dp[i][j][k]=,k<<=;
for(int st=;st<k;++st){
for(int i=;i<=n;++i)for(int j=;j<=m;++j)for(int s=st&st-;s;s=s-&st)
if(dp[i][j][st]>dp[i][j][s]+dp[i][j][st^s]-w[i][j])
dp[i][j][st]=dp[i][j][s]+dp[i][j][st^s]-w[i][j],pre[i][j][st]=i<<|j<<|s;
SPFA(st);
}
for(int i=;i<=n;++i)for(int j=;j<=m;++j)if(!w[i][j]){
dfs(i,j,k-);printf("%d\n",dp[i][j][k-]);
for(int i=;i<=n;++i,puts(""))for(int j=;j<=m;++j)putchar(w[i][j]?(v[i][j]?'o':'_'):'x');
return ;
}
}
难写所以没压行
最新文章
- Mesh Algorithm in OpenCascade
- div赋值,取值和input赋值，取值
- 加州大学伯克利分校Stat2.2x Probability 概率初步学习笔记: Section 4 The Central Limit Theorem
- 嵌入资源的方式让Winform使用系统没有的字体,无需安装字体
- Hadoop 2.x HDFS新特性
- uva 10048 Audiophobia(最小生成树）
- mongodb unset/set 删除/增加字段
- （转载）delphi 把图片存入数据库
- 软中断与硬中断 & 中断抢占 中断嵌套
- poj 3020Antenna Placement
- Swift—类的继承-备
- abiword Namespace List
- unity3d 导出 Excel
- JS判断是否在微信浏览器打开
- VS2010中使用Jquery调用Wcf服务读取数据库记录
- 跨主机网络overlay和macvlan模型
- Memcached服务加固方案
- leetcode Most Common Word——就是在考察自己实现split
- Ubuntu使用安装或者卸载软件！！！
- android--------微信 Tinker 热修复 （一）