模板 - DP动态规划

科技2022-07-13 132

整理的算法模板合集： ACM模板

一：【背包】

1.【01背包】

#include<algorithm> #include<cstdio> int T,n,i,j,v[110],w[110],f[1010]; int main(){ scanf("%d%d",&T,&n); for(i=1;i<=n;i++)scanf("%d%d",&v[i],&w[i]); for(i=1;i<=n;i++) for(j=T;j>=v[i];j--) f[j]=std::max(f[j],f[j-v[i]]+w[i]); printf("%d",f[T]); }

2.【完全背包】

#include<bits/stdc++.h> using namespace std; int T,n,ans,a[105],dp[30005]; int main(){ scanf("%d",&T); while(T--){ memset(dp,-127,sizeof(dp)); scanf("%d",&n);dp[0]=ans=0; for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++) for(int j=a[i];j<=25000;j++) dp[j]=max(dp[j],dp[j-a[i]]+1); for(int i=1;i<=n;++i)ans+=dp[a[i]]==1; printf("%d\n",ans); } }

3.【多人背包】

他们一共有 K 个人，每个人都会背一个包。这些包的容量是相同的，都是 V。可以装进背包里的一共有 N 种物品，每种物品都有给定的体积和价值。在 DD 看来，合理的背包安排方案是这样的：每个人背包里装的物品的总体积恰等于包的容量。每个包里的每种物品最多只有一件，但两个不同的包中可以存在相同的物品。任意两个人，他们包里的物品清单不能完全相同。在满足以上要求的前提下，所有包里的所有物品的总价值最大是多少呢？

#include<algorithm> #include<cstring> #include<cstdio> int ans,T,n,i,j,k,K,a,b,t,re[45],v[210],w[210],f[5010][45]; int main(){ scanf("%d%d%d",&K,&T,&n); memset(f,-127,sizeof(f));f[0][1]=0; for(i=1;i<=n;i++)scanf("%d%d",&v[i],&w[i]); for(i=1;i<=n;i++) for(j=T;j>=v[i];j--){ a=b=1,t=0; while(t<=K) if(f[j][a]>=f[j-v[i]][b]+w[i])re[++t]=f[j][a++]; else re[++t]=f[j-v[i]][b++]+w[i]; for(k=1;k<=K;k++)f[j][k]=re[k]; } for(i=1;i<=K;i++)ans+=f[T][i]; printf("%d",ans); }

4.【分组背包】

#include<algorithm> #include<cstdio> using namespace std; int T,n,i,j,a[65],s,t,r1,r2,r[65][3],v[65],w[65],f[32010]; int main(){ scanf("%d%d",&T,&n); v[0]=0xfffffff; for(i=1;i<=n;i++){ scanf("%d%d%d",&v[i],&s,&a[i]); if(a[i])r[a[i]][++r[a[i]][0]]=i;w[i]=v[i]*s; } for(i=1;i<=n;i++) for(j=T;j>=v[i]&&(!a[i]);j--){ t=j-v[i],r1=r[i][1],r2=r[i][2]; f[j]=max(f[j],f[t]+w[i]); if(v[r1]<=t)f[j]=max(f[j],f[t-v[r1]]+w[i]+w[r1]); if(v[r2]<=t)f[j]=max(f[j],f[t-v[r2]]+w[i]+w[r2]); if(v[r1]+v[r2]<=t)f[j]=max(f[j],f[t-v[r1]-v[r2]]+w[i]+w[r1]+w[r2]); } printf("%d",f[T]); }

5.【多重背包】

#include<algorithm> #include<cstring> #include<cstdio> #define Re register int using namespace std; const int N=103,M=4e4+3; int n,m,x,y,z,V,ans,v[N*17],w[N*17],dp[M]; inline void in(Re &x){ Re fu=0;x=0;char ch=getchar(); while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar(); while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=fu?-x:x; } int main(){ in(m),in(V); memset(dp,-127,sizeof(dp)); dp[0]=0; while(m--){ in(x),in(y),in(z);Re p=1; while(z>=p)v[++n]=y*p,w[n]=x*p,z-=p,p<<=1; if(z)v[++n]=y*z,w[n]=x*z; } for(Re i=1;i<=n;++i) for(Re j=V;j>=v[i];--j) dp[j]=max(dp[j],dp[j-v[i]]+w[i]); for(Re i=0;i<=V;++i)ans=max(ans,dp[i]); printf("%d\n",ans); }

6.【混合背包】

#include<algorithm> #include<cstdio> using namespace std; int x,a,b,c,d,T,n,i,j,t,f[1010],v[100010],w[100010]; int main(){ scanf("%d:%d%d:%d%d",&a,&b,&c,&d,&n); T=c*60+d-a*60-b; for(i=1;i<=n;i++){ scanf("%d%d%d",&a,&b,&c); if(!c){ for(j=0;j+a<=T;j++) f[j+a]=max(f[j+a],f[j]+b); continue; } x=1; while(c>=x){v[++t]=x*a,w[t]=x*b,c-=x,x<<=1;} v[++t]=c*a,w[t]=c*b; } for(i=1;i<=t;i++) for(j=T;j>=v[i];j--) f[j]=max(f[j],f[j-v[i]]+w[i]); printf("%d",f[T]); }

7.【二维费用】

#include<algorithm> #include<cstdio> using namespace std; int tmp,T1,T2,x,y,n,i,j,k,v1[105],v2[105],w[105],dp[105][105],ans[105][105]; int main(){ scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d%d%d",&v1[i],&v2[i],&w[i]); scanf("%d%d",&T1,&T2); for(i=1;i<=n;++i) for(j=T1;j>=v1[i];--j) for(k=T2;k>=v2[i];--k) if(dp[j][k]<(tmp=dp[j-v1[i]][k-v2[i]]+1)){ dp[j][k]=tmp; ans[j][k]=ans[j-v1[i]][k-v2[i]]+w[i]; } else if(dp[j][k]==tmp)ans[j][k]=min(ans[j][k],ans[j-v1[i]][k-v2[i]]+w[i]); printf("%d",ans[T1][T2]); }

二：【树形DP】

(1).【简单树形 DP】

#include<algorithm> #include<cstring> #include<cstdio> #define R register int using namespace std; int head[6010],a,b,t,i,j,n,f[6010][2],pan[6010]; struct QAQ{int next,to;}Q[6010]; inline void add(int x,int y){Q[++t].to=y,Q[t].next=head[x],head[x]=t;} inline void dfs(int w){ for(R k=head[w];k;k=Q[k].next){ int to=Q[k].to; dfs(to); f[w][0]+=max(f[to][0],f[to][1]); f[w][1]+=f[to][0]; } } int main(){ scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&f[i][1]); for(i=1;i<n;i++)scanf("%d%d",&a,&b),pan[a]++,add(b,a); for(i=1;i<=n;i++) if(!pan[i]){ dfs(i); printf("%d\n",max(f[i][0],f[i][1])); return 0; } }

(2).【换根 DP】

每个奶牛居住在 N 个农场中的一个，这些农场由 N−1 条道路连接，并且从任意一个农场都能够到达另外一个农场。道路 i 连接农场 $A_i$ 和 $B_i$ ，长度为 $L_i$ 。集会可以在 N 个农场中的任意一个举行。另外，每个牛棚中居住着 $C_i$ 只奶牛。在选择集会的地点的时候，Bessie 希望最大化方便的程度（也就是最小化不方便程度）。比如选择第 X 个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和（比如，农场 i 到达农场 X 的距离是 20，那么总路程就是 $C_i\times 20$ 。帮助 Bessie 找出最方便的地点来举行大集会。

#include<algorithm> #include<cstring> #include<cstdio> #define LL long long #define Re register int using namespace std; const LL N=1e5+3,inf=1e18; int n,m,x,y,z,o,A[N],S[N],dis[N],size[N],head[N];LL ans=inf,f[N],g[N]; struct QAQ{int w,to,next;}a[N<<1]; inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;} inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } inline void dfs1(Re x,Re fa){ size[x]=1,S[x]=A[x]; for(Re i=head[x],to;i;i=a[i].next)if((to=a[i].to)!=fa) dis[to]=a[i].w,dfs1(to,x),S[x]+=S[to],size[x]+=size[to],f[x]+=f[to]+(LL)S[to]*a[i].w; } inline void dfs2(Re x,Re fa){ if(fa)g[x]=g[fa]+f[fa]-f[x]-(LL)S[x]*dis[x]+(LL)(S[1]-S[x])*dis[x]; for(Re i=head[x],to;i;i=a[i].next)if((to=a[i].to)!=fa)dfs2(to,x); ans=min(ans,f[x]+g[x]); } int main(){ // freopen("123.txt","r",stdin); in(n),m=n-1; for(Re i=1;i<=n;++i)in(A[i]); while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z); dfs1(1,0),dfs2(1,0),printf("%lld\n",ans); }

三：【数位DP】

不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。windy 想知道，在 a 和 b 之间，包括 a 和 b ，总共有多少个 windy 数？

1.【dfs】

#include<cstring> #include<cstdio> #include<cmath> #define R register int using namespace std; int a,b,l,num[12],dp[12][10]; inline int dfs(int len,int up,int ok){ R i,ed,ans=0; if(len<1)return 1; if(!ok&&~dp[len][up]&&up!=-7)return dp[len][up]; ed=ok?num[len]:9; for(i=0;i<=ed;i++)if(abs(i-up)>=2) ans+=dfs(len-1,(!i&&up==-7)?up:i,ok&&(i==ed)); if(!ok&&up!=-7)dp[len][up]=ans; return ans; } inline int sovle(int x){ l=0; while(x)num[++l]=x%10,x/=10; return dfs(l,-7,1); } int main(){ scanf("%d%d",&a,&b); memset(dp,-1,sizeof(dp)); printf("%d",sovle(b)-sovle(a-1)); }

2.【dp】

#include<cstdio> #include<cmath> #define R register int using namespace std; int i,j,k,a,b,l,ans,num[12],dp[12][10]; inline int dpp(int len){ ans=0; for(i=1;i<len;i++) for(j=1;j<10;j++) ans+=dp[i][j]; for(j=1;j<num[len];j++)ans+=dp[len][j]; for(i=len-1;i>0;i--){ for(j=0;j<num[i];j++) if(abs(num[i+1]-j)>=2)ans+=dp[i][j]; if(abs(num[i]-num[i+1])<2)break; } if(!i)ans++; return ans; } inline int sovle(int x){ l=0; while(x)num[++l]=x%10,x/=10; return dpp(l); } inline int sakura(){ scanf("%d%d",&a,&b); for(i=0;i<10;i++)dp[1][i]=1; for(i=2;i<11;i++) for(j=0;j<10;j++) for(k=0;k<10;k++) if(abs(j-k)>=2) dp[i][j]+=dp[i-1][k]; printf("%d",sovle(b)-sovle(a-1)); } int QAQWQ=sakura(); int main(){}

四：【DP 的优化】

1.【二分】最长公共子序列

#include<bits/stdc++.h> using namespace std; int pan[100010],b[100010],f[100010],n,i,a,len=1,l,r,mid; inline int in(){ int x=0,fh=1;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*fh; } int main(){ n=in(); for(i=1;i<=n;i++)a=in(),pan[a]=i,f[i]=0xfffffff; for(i=1;i<=n;i++)a=in(),b[i]=pan[a]; f[1]=b[1]; for(i=2;i<=n;i++){ l=0;r=len; if(b[i]>f[len])f[++len]=b[i]; else{ while(l<r){ mid=(l+r)/2; if(f[mid]<b[i])l=mid+1; else r=mid; } f[l]=min(b[i],f[l]); } } printf("%d",len); }

2.【二进制优化多重背包】

#include<algorithm> #include<cstdio> #define Re register int using namespace std; const int N=103,M=4e4+3,logN=17; int m,n,x,y,z,V,ans,v[N*logN],w[N*logN],dp[M]; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } int main(){ in(m),in(V); for(Re i=1;i<=m;++i){ in(x),in(y),in(z); for(Re j=1;j<=z;j<<=1)z-=j,w[++n]=x*j,v[n]=y*j; if(z)w[++n]=x*z,v[n]=y*z; } for(Re i=1;i<=n;++i) for(Re j=V;j>=v[i];--j) dp[j]=max(dp[j],dp[j-v[i]]+w[i]); for(Re j=0;j<=V;++j)ans=max(ans,dp[j]); printf("%d\n",ans); }

3.【单调队列优化多重背包】

#include<cstdio> #define Re register int const int N=7003,M=7003; int n,h,t,V,mp,tmp,v[N],w[N],c[N],Q[N],K[N],dp[M]; inline void in(Re &x){ Re fu=0;x=0;char ch=getchar(); while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar(); while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=fu?-x:x; } inline int max(Re a,Re b){return a>b?a:b;} inline int min(Re a,Re b){return a<b?a:b;} int main(){ in(n),in(V); for(Re i=1;i<=n;++i)in(v[i]),in(w[i]),in(c[i]); for(Re i=1;i<=n;++i) for(Re r=0;r<v[i];++r){ h=1,t=0,mp=(V-r)/v[i]; for(Re p=0;p<=mp;++p){ tmp=dp[p*v[i]+r]-w[i]*p; while(h<=t&&Q[t]<=tmp)--t; Q[++t]=tmp,K[t]=p; while(h<=t&&p-K[h]>min(c[i],V/v[i]))++h; dp[p*v[i]+r]=max(dp[p*v[i]+r],Q[h]+p*w[i]); } } printf("%d",dp[V]); }

4.【矩阵加速递推】【学习笔记】动态规划—矩阵递推加速 5.【四边形不等式优化】【模板】 (1).【分治】

#include<algorithm> #include<cstdio> #include<cmath> #define Re register int using namespace std; const int N=5e5+3; int i,j,n,h,t,a[N],Q[N],Poi[N]; double tmp,p[N],sqr[N]; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } inline void sakura(Re l,Re r,Re L,Re R){ if(l>r)return; Re mid=l+r>>1,j0;double mx=0; for(Re j=L;j<=mid&&j<=R;++j) //暴力找p[i]的最优决策点j0，而其决策点j必须满足j<=i，即此处的j<=mid if((tmp=a[j]+sqr[mid-j])>mx)mx=tmp,j0=j; p[mid]=max(p[mid],mx); sakura(l,mid-1,L,j0),sakura(mid+1,r,j0,R); } int main(){ in(n); for(Re i=1;i<=n;++i)in(a[i]),sqr[i]=sqrt(i); sakura(1,n,1,n); for(Re i=1;i<n-i+1;++i)swap(a[i],a[n-i+1]),swap(p[i],p[n-i+1]); sakura(1,n,1,n); for(Re i=n;i;--i)printf("%d\n",(int)ceil(p[i])-a[i]); }

(2).【二分栈】

#include<algorithm> #include<cstdio> #include<cmath> #define Re register int using namespace std; const int N=5e5+3; int i,j,n,h,t,a[N],Q[N],Poi[N]; double p[N],sqr[N]; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } inline double Y(Re i,Re j){return a[j]+sqr[i-j];} inline int find_Poi(int j1,int j2){//找到两个直线的交点i Re l=j2,r=n,mid,ans=n+1;//为了处理两个直线没有交点的情况，用一个变量记录答案 while(l<=r){ mid=l+r>>1; if(Y(mid,j1)<=Y(mid,j2))ans=mid,r=mid-1; //当前这个位置i使得直线j1的纵坐标小于直线j2的纵坐标，说明这个点i在交点的右方，所以右边界要缩小 else l=mid+1; } return ans; } inline void sakura(){ h=1,t=0; for(i=1;i<=n;++i){//由于i本身也是一个决策点，所以要先入队再取答案择优 while(h<t&&Poi[t-1]>=find_Poi(Q[t],i))--t;//如果出现了上述可踢的情况，出队 Poi[t]=find_Poi(Q[t],i),Q[++t]=i; while(h<t&&Poi[h]<=i)++h; //找到第一个位置j使得直线Q[j]与直线Q[j+1]的交点大于i， //那么直线Q[j]就是i前面在最上面的直线，即答案，自己画个图模拟一下就懂了 p[i]=max(p[i],Y(i,Q[h])); } } int main(){ in(n); for(Re i=1;i<=n;++i)in(a[i]),sqr[i]=sqrt(i); sakura(); for(Re i=1;i<n-i+1;++i)swap(a[i],a[n-i+1]),swap(p[i],p[n-i+1]); sakura(); for(Re i=n;i;--i)printf("%d\n",(int)ceil(p[i])-a[i]); }

6.【斜率优化】

(1).【单调队列（x 与 k 均单调）】

#include<cstring> #include<cstdio> #define LL long long #define Re register LL const int N=5e4+5; LL i,j,n,L,h=1,t=0,Q[N],S[N],dp[N]; //S[n]=∑C[i]+1, dp[i]=min(dp[j]+(S[i]-(S[j]+L+1))^2)，++L //dp[i]=S[i]^2-2*S[i]*L+dp[j]+(S[j]+L)^2-2S[i]*S[j] //(2*S[i]) * S[j] + (dp[i]-S[i]^2+2S[i]L)=(dp[j]+(S[j]+L)^2) // k * x + b = y inline LL min(Re a,Re b){return a<b?a:b;} inline LL X(Re j){return S[j];} inline LL Y(Re j){return dp[j]+(S[j]+L)*(S[j]+L);} inline long double slope(Re i,Re j){return (long double)(Y(j)-Y(i))/(X(j)-X(i));}//记得开long double int main(){ scanf("%lld%lld",&n,&L);++L; for(i=1;i<=n;S[i]+=S[i-1]+1,++i)scanf("%lld",&S[i]); Q[++t]=0;//重中之重 for(i=1;i<=n;++i){ while(h<t&&slope(Q[h],Q[h+1])<=2*S[i])++h;//至少要有两个元素 h<t。出队判断时尽量加上等号 dp[i]=dp[j=Q[h]]+(S[i]-S[j]-L)*(S[i]-S[j]-L); while(h<t&&slope(Q[t-1],Q[t])>=slope(Q[t-1],i))--t;//至少要有两个元素 h<t。入队判断时尽量加上等号 Q[++t]=i; } printf("%lld",dp[n]); }

(2).【二分+单调队列（x 单调 k 不单调）】

#include<cstring> #include<cstdio> #define LL long long #define Re register LL const int N=3e5+5; LL i,j,n,h=1,t=0,S,Q[N],ST[N],SF[N],dp[N]; //dp[p][i]=min(dp[p-1][j]+(ST[i]+S*p)*(SF[i]-SF[j])); //dp[i]=dp[j]+ST[i]*(SF[i]-SF[j])+S*(SF[n]-SF[j]); //(S+ST[i]) * SF[j] + (dp[i]-ST[i]*SF[i]-S*SF[i]) = (dp[j]) // k * x + b = y //ti可小于0，所以ST[i]非递增，只可二分 //fi可等于0，所以SF[i](X)非严格递增，因此需要特判X(i)==X(j)的情况 inline LL min(Re a,Re b){return a<b?a:b;} inline LL X(Re j){return SF[j];} inline LL Y(Re j){return dp[j];} inline long double slope(Re i,Re j){return X(j)==X(i)?(Y(j)>=Y(i)?1e18:-1e18):(long double)(Y(j)-Y(i))/(X(j)-X(i));} //由于需要二分查找，多了一些限制：队列里不能有在同一位置的点,返回inf还是-inf都影响着是否删除重点，平时不可不管，二分必须注意返回值 inline LL sakura(Re k){ if(h==t)return Q[h]; Re l=h,r=t; while(l<r){ Re mid=l+r>>1,i=Q[mid],j=Q[mid+1]; if(slope(i,j)<k)l=mid+1; // if( (Y(j) - Y(i)) < k * (X(j) - X(i)) )l=mid+1;//注意是(j)-(i)因为Q[mid+1]>Q[mid]s即j>i即SF[j]>SF[i]即X(j)>X(i)，如果是(i)-(j)的话乘过去要变号 else r=mid; } return Q[l]; } int main(){ scanf("%lld%lld",&n,&S); for(i=1;i<=n;ST[i]+=ST[i-1],SF[i]+=SF[i-1],++i)scanf("%lld%lld",&ST[i],&SF[i]); Q[++t]=0; for(i=1;i<=n;++i){ j=sakura(S+ST[i]); dp[i]=dp[j]+ST[i]*(SF[i]-SF[j])+S*(SF[n]-SF[j]); while(h<t&&slope(Q[t-1],Q[t])>=slope(Q[t-1],i))--t;//此处取等号作用出现，如果不取等会WA Q[++t]=i; } printf("%lld",dp[n]); }

(3).【CDQ（x 与 k 均不单调）】

#include<algorithm> #include<cstring> #include<cstdio> #define LD long double #define LL long long #define Re register int #define S2(a) (1ll*(a)*(a)) using namespace std; const LL N=1e5+3,inf=1e18; int n,H[N],W[N],Q[N];LL S[N],dp[N]; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } //dp[i]=min(dp[i],dp[j]+(H[i]-H[j])*(H[i]-H[j])+S[i-1]-S[j]); //dp[i]=dp[j]-2*H[i]*H[j]+H[j]*H[j]+H[i]*H[i]+S[i-1]-S[j] //(2*H[i]) * H[j] + (dp[i]-S[i-1]-H[i]*H[i]) = (dp[j]+H[j]*H[j]-S[j]) // k * x + b = y #define X(j) (a[j].x) #define Y(j) (a[j].y) struct QAQ{ int k,x,id;LL y; inline bool operator<(const QAQ &O)const{return x!=O.x?x<O.x:y<O.y;} }a[N],b[N]; inline bool cmp(QAQ A,QAQ B){return A.k<B.k;} inline LD slope(Re i,Re j){return X(i)==X(j)?(Y(j)>Y(i)?inf:-inf):(LD)(Y(j)-Y(i))/(X(j)-X(i));} inline void CDQ(Re L,Re R){ if(L==R){Re j=a[L].id;a[L].y=dp[j]+(LL)H[j]*H[j]-S[j];return;} Re mid=L+R>>1,p1=L,p2=mid+1,h=1,t=0; for(Re i=L;i<=R;++i)a[i].id<=mid?b[p1++]=a[i]:b[p2++]=a[i]; for(Re i=L;i<=R;++i)a[i]=b[i]; CDQ(L,mid); for(Re i=L;i<=mid;++i){ while(h<t&&slope(Q[t-1],Q[t])>=slope(Q[t-1],i))--t; Q[++t]=i; } for(Re i=mid+1,j,id;i<=R;++i){ while(h<t&&slope(Q[h],Q[h+1])<=a[i].k)++h; if(h<=t)id=a[i].id,j=Q[h],dp[id]=min(dp[id],a[j].y-(LL)a[i].k*a[j].x+S[id-1]+(LL)H[id]*H[id]); } CDQ(mid+1,R); Re w=L-1;p1=L,p2=mid+1; while(p1<=mid&&p2<=R)b[++w]=a[p1]<a[p2]?a[p1++]:a[p2++]; while(p1<=mid)b[++w]=a[p1++];while(p2<=R)b[++w]=a[p2++]; for(Re i=L;i<=R;++i)a[i]=b[i]; } int main(){ // freopen("123.txt","r",stdin); in(n); for(Re i=1;i<=n;++i)in(H[i]); for(Re i=1;i<=n;++i)in(W[i]); for(Re i=1;i<=n;++i)S[i]=S[i-1]+W[i],dp[i]=inf; for(Re i=1;i<=n;++i)a[i].k=(H[i]<<1),a[i].x=H[i],a[i].id=i; sort(a+1,a+n+1,cmp); dp[1]=0,CDQ(1,n); printf("%lld\n",dp[n]); }

(4).【Splay 维护动态凸包（x 与 k 均不单调）】

五：【插头 DP】

1.【多回路插头 DP】

给出n*m的方格，有些格子不能铺线，其它格子必须铺，可以形成多个闭合回路。问有多少种铺法？从第2行到第n+1行，每行m个数字（1 or 0），1表铺线，0表不铺线

#include<algorithm> #include<cstring> #include<cstdio> #define LL long long #define Re register int using namespace std; const int N=15,M=8192+3; int n,m,o,V,T,A[N][N];LL dp[2][M]; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } int main(){ // freopen("123.txt","r",stdin); in(T); while(T--){ in(n),in(m),V=(1<<m+1)-1; for(Re i=1;i<=n;++i) for(Re j=1;j<=m;++j) in(A[i][j]); for(Re j=0;j<=V;++j)dp[0][j]=dp[1][j]=0; dp[o][0]=1; for(Re i=1;i<=n;++i){ o^=1; for(Re s=0;s<=V;++s)dp[o][s]=(s&1)?0:dp[o^1][s>>1];//把线拉下来 for(Re j=1;j<=m;++j){ o^=1; for(Re s=0;s<=V;++s)dp[o][s]=0; for(Re s=0;s<=V;++s)if(dp[o^1][s]){ Re L=(s>>j-1)&1,U=(s>>j+1-1)&1; if(A[i][j]){//可以铺线 dp[o][s^(1<<j-1)^(1<<j+1-1)]+=dp[o^1][s];//横和竖和左上拐和右下拐 if(L!=U)dp[o][s]+=dp[o^1][s];//左下拐和右上拐 } else{//不可以铺线 if(!L&&!U)dp[o][s]+=dp[o^1][s];//无插头才可以转移 } } } } printf("%lld\n",dp[o][0]); } }

2.【单回路插头 DP】 (1).【括号表示法】

#include<algorithm> #include<cstring> #include<cstdio> #define LL long long #define Re register int using namespace std; const int N=14,M=1594323+3; int n,m,o,V,edx,edy,Mi[N],A[N][N];LL ans,dp[2][M];char s[N]; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } int main(){ // freopen("123.txt","r",stdin); in(n),in(m),Mi[0]=1; for(Re i=1;i<=m+1;++i)Mi[i]=Mi[i-1]*3;V=Mi[m+1]-1; for(Re i=1;i<=n;++i){ scanf("%s",s+1); for(Re j=1;j<=m;++j)if(!(A[i][j]=(s[j]=='*')))edx=i,edy=j; } // printf("edx=%d, edy=%d\n",edx,edy); dp[o][0]=1; for(Re i=1;i<=n;++i){ o^=1; for(Re s=0;s<=V;++s)dp[o][s]=s%3?0:dp[o^1][s/3]; for(Re j=1;j<=m;++j){ o^=1; for(Re s=0;s<=V;++s)dp[o][s]=0; for(Re s=0;s<=V;++s)if(dp[o^1][s]){ Re L=s/Mi[j-1]%3,U=s/Mi[j+1-1]%3; if(A[i][j]){if(!L&&!U)dp[o][s]+=dp[o^1][s];} else if(!L&&!U)dp[o][s+Mi[j-1]+2*Mi[j+1-1]]+=dp[o^1][s]; else if(!L&&U)dp[o][s]+=dp[o^1][s],dp[o][s+U*Mi[j-1]-U*Mi[j+1-1]]+=dp[o^1][s]; else if(L&&!U)dp[o][s]+=dp[o^1][s],dp[o][s-L*Mi[j-1]+L*Mi[j+1-1]]+=dp[o^1][s]; else if(L==1&&U==1){ Re cnt=1; for(Re k=j+2;k<=m;++k){ if(s/Mi[k-1]%3==1)++cnt; else if(s/Mi[k-1]%3==2)--cnt; if(!cnt){dp[o][s-Mi[j-1]-Mi[j+1-1]-Mi[k-1]]+=dp[o^1][s];break;}//2变1 } } else if(L==2&&U==2){ Re cnt=1; for(Re k=j-1;k>=1;--k){ if(s/Mi[k-1]%3==1)--cnt; else if(s/Mi[k-1]%3==2)++cnt; if(!cnt){dp[o][s-2*Mi[j-1]-2*Mi[j+1-1]+Mi[k-1]]+=dp[o^1][s];break;}//1变2 } } else if(L==2&&U==1)dp[o][s-2*Mi[j-1]-Mi[j+1-1]]+=dp[o^1][s]; else if(L==1&&U==2)if(i==edx&&j==edy&&!(s-Mi[j-1]-2*Mi[j+1-1]))ans+=dp[o^1][s]; } } } printf("%lld\n",ans); }

(2).【括号表示法+优化状态枚举】【模板】插头 dp

#include<algorithm> #include<cstring> #include<cstdio> #define LL long long #define Re register int using namespace std; const int N=14,M=1594323+3; int n,m,o,V,edx,edy,Mi[N],A[N][N];LL ans,dp[2][M];char s[N]; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } int st[2][M]; inline void add(Re s,LL v){ if(!dp[o][s])st[o][++st[o][0]]=s; dp[o][s]+=v; } inline void CL(){ for(Re i=1;i<=st[o][0];++i)dp[o][st[o][i]]=0; st[o][0]=0; } int main(){ // freopen("123.txt","r",stdin); in(n),in(m),Mi[0]=1; for(Re i=1;i<=m+1;++i)Mi[i]=Mi[i-1]*3;V=Mi[m+1]-1; for(Re i=1;i<=n;++i){ scanf("%s",s+1); for(Re j=1;j<=m;++j)if(!(A[i][j]=(s[j]=='*')))edx=i,edy=j; } // printf("edx=%d, edy=%d\n",edx,edy); dp[o][st[o][++st[o][0]]=0]=1; for(Re i=1;i<=n;++i){ o^=1,CL(); for(Re I=1;I<=st[o^1][0];++I)if(st[o^1][I]*3<=V&&dp[o^1][st[o^1][I]]) dp[o][st[o][++st[o][0]]=st[o^1][I]*3]=dp[o^1][st[o^1][I]]; for(Re j=1;j<=m;++j){ o^=1,CL(); for(Re I=1;I<=st[o^1][0];++I)if(dp[o^1][st[o^1][I]]){ Re s=st[o^1][I];LL v=dp[o^1][s]; Re L=s/Mi[j-1]%3,U=s/Mi[j+1-1]%3; if(A[i][j]){if(!L&&!U)add(s,v);} else if(!L&&!U)add(s+Mi[j-1]+2*Mi[j+1-1],v); else if(!L&&U)add(s,v),add(s+U*Mi[j-1]-U*Mi[j+1-1],v); else if(L&&!U)add(s,v),add(s-L*Mi[j-1]+L*Mi[j+1-1],v); else if(L==1&&U==1){ Re cnt=1; for(Re k=j+2;k<=m;++k){ if(s/Mi[k-1]%3==1)++cnt; else if(s/Mi[k-1]%3==2)--cnt; if(!cnt){add(s-Mi[j-1]-Mi[j+1-1]-Mi[k-1],v);break;}//2变1 } } else if(L==2&&U==2){ Re cnt=1; for(Re k=j-1;k>=1;--k){ if(s/Mi[k-1]%3==1)--cnt; else if(s/Mi[k-1]%3==2)++cnt; if(!cnt){add(s-2*Mi[j-1]-2*Mi[j+1-1]+Mi[k-1],v);break;}//1变2 } } else if(L==2&&U==1)add(s-2*Mi[j-1]-Mi[j+1-1],v); else if(L==1&&U==2)if(i==edx&&j==edy&&!(s-Mi[j-1]-2*Mi[j+1-1]))ans+=v; } } } printf("%lld\n",ans); }

Processed: 0.016, SQL: 8