怕不是最后一篇（雾），过滤最基础的背包DP、状压DP、递推等
树上换根DP：https://www.luogu.org/problemnew/show/P4284
#include<bits/stdc++.h> using namespace std; typedef long double ld; const int N=5e5+7; int n,cnt,hd[N],v[N<<1],nxt[N<<1]; ld ans,p[N],f[N],g[N],w[N<<1]; void add(int x,int y,ld z){v[++cnt]=y,nxt[cnt]=hd[x],w[cnt]=z,hd[x]=cnt;} void dfs1(int u,int fa) { f[u]=p[u]; for(int i=hd[u];i;i=nxt[i]) if(v[i]!=fa)dfs1(v[i],u),f[u]=(f[u]+w[i]*f[v[i]]*(1-f[u])); } void dfs2(int u,int fa,ld p) { g[u]=f[u]+(fabs(1-p*f[u])>1e-7?p*(g[fa]-p*f[u])/(1-p*f[u])*(1-f[u]):0); for(int i=hd[u];i;i=nxt[i])if(v[i]!=fa)dfs2(v[i],u,w[i]); } int main() { scanf("%d",&n); for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),add(x,y,z*0.01),add(y,x,z*0.01); for(int i=1,x;i<=n;i++)scanf("%d",&x),p[i]=x*0.01; dfs1(1,0),dfs2(1,0,0); for(int i=1;i<=n;i++)ans+=g[i]; printf("%0.6Lf",ans); }
数位DP：http://www.51nod.com/Challenge/Problem.html#!#problemId=1245
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,p,a[70],f[2][70][70]; int tot,pos; int main() { int T;cin>>T; while(T--) { cin>>n>>p; tot=0; while(n)a[tot++]=n%p,n/=p; tot--; memset(f[pos],0,sizeof f[pos]); f[pos][0][0]=a[0]+1,f[pos][1][1]=p-f[pos][0][0]; for(int i=1;i<=tot;i++) { pos^=1; memset(f[pos],0,sizeof f[pos]); for(int j=0;j<=tot;j++) { f[pos][j][0]+=(a[i]+1)*f[pos^1][j][0]+a[i]*f[pos^1][j][1]; f[pos][j+1][1]+=(p-a[i]-1)*f[pos^1][j][0]+(p-a[i])*f[pos^1][j][1]; } } while(!f[pos][tot][0])tot--; for(int i=0;i<=tot;i++)printf("%lld ",f[pos][i][0]); puts(""); } }
斜率优化DP：https://www.luogu.org/problemnew/show/P3628
#include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=1e6+100; int n,a,b,c,q[maxn],qs,qe; ll s[maxn],f[maxn]; double val(int j,int k) {return (f[j]-f[k]+a*(s[j]*s[j]-s[k]*s[k])+b*(s[k]-s[j]))*1.0/(2*a*(s[j]-s[k]));} int main() { scanf("%d%d%d%d",&n,&a,&b,&c); for(int i=1;i<=n;i++) { int x; scanf("%d",&x); s[i]=s[i-1]+x; } for(int i=1;i<=n;i++) { while(qs<qe&&val(q[qs+1],q[qs])<s[i]) qs++; f[i]=f[q[qs]]+a*(s[i]-s[q[qs]])*(s[i]-s[q[qs]])+b*(s[i]-s[q[qs]])+c; while(qs<qe&&val(i,q[qe])<val(q[qe],q[qe-1])) qe--; q[++qe]=i; } printf("%lld",f[n]); }
决策单调性DP（最值分治）：https://www.lydsy.com/JudgeOnline/problem.php?id=2216
#include<bits/stdc++.h> using namespace std; const int N=5e5+7; int n,a[N],ans[2][N]; double calc(int u,int v){return sqrt(abs(v-u))+a[u];} void solve(int l,int r,int ql,int qr,int ans[N]) { if(l>r||ql>qr)return; int minp=l,mid=ql+qr>>1; double mn=calc(l,mid),ret=0; for(int i=l+1;i<=r&&i<=mid;i++) { ret=calc(i,mid); if(mn<=ret)mn=ret,minp=i; } ans[mid]=max(ans[mid],int(ceil(mn))-a[mid]); solve(l,minp,ql,mid-1,ans),solve(minp,r,mid+1,qr,ans); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); solve(1,n,1,n,ans[0]); for(int i=1;i<=n/2;i++)swap(a[i],a[n-i+1]); solve(1,n,1,n,ans[1]); for(int i=1;i<=n;i++)printf("%d ",max(ans[0][i],ans[1][n-i+1])); }
四边形优化DP：http://acm.hdu.edu.cn/showproblem.php?pid=3506
#include<cstdio> #include<algorithm> using namespace std; const int N=2018; int n,val[N],sum[N],f[N][N],s[N][N]; void solve() { for(int i=1;i<=2*n;i++)f[i][i]=0,s[i][i]=i; for(int len=2;len<=n;len++) for(int i=2*n-len;i;i--) { int j=i+len-1; f[i][i+len-1]=1e9; int a=s[i][i+len-2],b=s[i+1][i+len-1],cost=sum[i+len-1]-sum[i-1]; for(int k=a;k<=b;k++) if(f[i][i+len-1]>f[i][k]+f[k+1][i+len-1]+cost) { f[i][i+len-1]=f[i][k]+f[k+1][i+len-1]+cost; s[i][i+len-1]=k; } } } int main() { while(~scanf("%d",&n)) { for(int i=1;i<=n;i++)scanf("%d",&val[i]),val[i+n]=val[i]; for(int i=1;i<=2*n;i++)sum[i]=sum[i-1]+val[i]; solve(); int ans=1e9; for(int i=1;i<=n;i++)ans=min(ans,f[i][i+n-1]); printf("%d ",ans); } }
Min-Max容斥：https://loj.ac/problem/2542
#include<bits/stdc++.h> using namespace std; const int mod=998244353,N=3e5; int n,Q,s,cnt,f[N],sz[N],k[20],d[20],du[20],hd[20],v[40],nxt[40]; int qpow(int a,int b) { int ret=1; while(b) { if(b&1)ret=1ll*ret*a%mod; a=1ll*a*a%mod;b/=2; } return ret; } void add(int x,int y){v[++cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt;} void dfs(int u,int fa,int S) { if(S&(1<<u-1)){k[u]=d[u]=0;return;} k[u]=d[u]=du[u]; for(int i=hd[u];i;i=nxt[i]) if(v[i]!=fa) { dfs(v[i],u,S); k[u]=(k[u]-k[v[i]])%mod; d[u]=(d[u]+d[v[i]])%mod; } k[u]=qpow(k[u],mod-2); d[u]=1ll*d[u]*k[u]%mod; } int main() { scanf("%d%d%d",&n,&Q,&s); for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x),du[x]++,du[y]++; for(int i=0;i<(1<<n);i++) dfs(s,0,i),f[i]=d[s],sz[i]=sz[i>>1]+(i&1); while(Q--) { int k,S=0; scanf("%d",&k); for(int i=1,x;i<=k;i++)scanf("%d",&x),S|=1<<x-1; int ans=0; for(int i=S;i;i=(i-1)&S) ans=(sz[i]&1)?(ans+f[i])%mod:(ans-f[i])%mod; printf("%d ",(ans+mod)%mod); } }
动态DP：https://www.luogu.org/problemnew/show/P5024
#include<bits/stdc++.h> #define lson l,mid,rt*2 #define rson mid+1,r,rt*2+1 using namespace std; typedef long long ll; const int N=2e6+7; struct mat{ ll f[2][2]; mat(){f[0][0]=f[0][1]=f[1][0]=f[1][1]=0;} friend mat operator+(mat a,mat b) { mat c; for(int i=0;i<2;i++) for(int j=0;j<2;j++) c.f[i][j]=min(a.f[i][1]+min(b.f[0][j],b.f[1][j]),a.f[i][0]+b.f[1][j]); return c; } }st[N],to; int n,m,cnt,dep[N],tid[N],bel[N],fa[N],sz[N],son[N],dfn[N],pos[N]; ll p[N],f[N],g[N],cf[N],cg[N]; bool used[N]; vector<int>G[N]; void build(int l,int r,int rt) { used[rt]=bel[tid[l]]==bel[tid[r]]; if(l==r)return; int mid=(l+r)/2; build(lson); build(rson); } void modify(int l,int r,int rt,int p) { if(l==r){st[rt]=to;return;} int mid=(l+r)/2; if(p<=mid)modify(lson,p); else modify(rson,p); if(used[rt])st[rt]=st[rt*2]+st[rt*2+1]; } mat query(int l,int r,int rt,int L,int R) { if(L==l&&r==R)return st[rt]; int mid=(l+r)/2; if(R<=mid)return query(lson,L,R); if(L>mid)return query(rson,L,R); return query(lson,L,mid)+query(rson,mid+1,R); } void dfs(int u) { sz[u]=1; dep[u]=dep[fa[u]]+1; for(int i=0;i<G[u].size();i++) if(G[u][i]!=fa[u]) { fa[G[u][i]]=u; dfs(G[u][i]); sz[u]+=sz[G[u][i]]; if(sz[G[u][i]]>sz[son[u]])son[u]=G[u][i]; } } void repos(int u) { to.f[1][1]=cf[u],to.f[0][0]=cg[u],to.f[0][1]=to.f[1][0]=1ll<<40; modify(1,n,1,dfn[u]); } void dfs(int u,int tp) { bel[u]=tp; pos[bel[u]]=dfn[u]=++cnt; tid[cnt]=u; cf[u]+=p[u]; f[u]+=p[u]; if(son[u])dfs(son[u],tp); for(int i=0;i<G[u].size();i++) if(G[u][i]!=fa[u]) { if(G[u][i]!=son[u])dfs(G[u][i],G[u][i]); f[u]+=min(f[G[u][i]],g[G[u][i]]); g[u]+=f[G[u][i]]; } if(bel[u]==u)cf[fa[u]]+=min(f[u],g[u]),cg[fa[u]]+=f[u]; repos(u); } void update(int x) { while(x) { int b=bel[x]; ll mn1=min(f[b],g[b]),mn2=f[b]; cf[fa[b]]-=mn1; cg[fa[b]]-=mn2; repos(x); mat it=query(1,n,1,dfn[b],pos[b]); f[b]=min(it.f[1][0],it.f[1][1]); g[b]=min(it.f[0][0],it.f[0][1]); cf[fa[b]]+=min(f[b],g[b]); cg[fa[b]]+=f[b]; if(f[b]==mn2&&min(f[b],g[b])==mn1)break; x=fa[bel[x]]; } } int main() { scanf("%d%d%*s",&n,&m); for(int i=1;i<=n;i++)scanf("%lld",&p[i]); for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x); build(1,n,1); dfs(1); dfs(1,1); build(1,n,1); while(m--) { int a,x,b,y; scanf("%d%d%d%d",&a,&x,&b,&y); if((fa[a]==b||fa[b]==a)&&x+y==0){puts("-1");continue;} (x?cg[a]:cf[a])+=1ll<<40,update(a); (y?cg[b]:cf[b])+=1ll<<40,update(b); ll ans=min(cf[0],cg[0]); (x?cg[a]:cf[a])-=1ll<<40,update(a); (y?cg[b]:cf[b])-=1ll<<40,update(b); printf("%lld ",ans); } }
自动机上DP：https://www.luogu.org/problemnew/show/P5279
#include<bits/stdc++.h> using namespace std; const int N=5005,mod=998244353; int n,tot,ans,c[5][5],fac[N],inv[N],has[N],f[2][N][405],ch[N][5]; struct node{ int f[2][3][3],cnt; node(){memset(f,-1,sizeof f),f[0][0][0]=cnt=0;} bool operator<(const node&x)const { for(int i=0;i<2;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) if(f[i][j][k]!=x.f[i][j][k])return f[i][j][k]<x.f[i][j][k]; return cnt<x.cnt; } }st[N]; void add(int&a,long long b){a=(a+b)%mod;} map<node,int>S; node trans(node u,int x) { node ret; ret.cnt=min(u.cnt+(x>=2),7); for(int a=0;a<2;a++) for(int b=0;a+b<2;b++) for(int i=0;i<3;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) if(i+j+k+b*2<=x&&u.f[a][i][j]!=-1) ret.f[a+b][j][k]=max(ret.f[a+b][j][k],min(u.f[a][i][j]+i+(x-i-j-k-b*2)/3,4)); return ret; } int dfs(node u) { if(S.count(u))return S[u]; if(u.cnt==7)return 0; for(int i=0;i<3;i++)for(int j=0;j<3;j++)if(u.f[1][i][j]==4)return 0; st[++tot]=u,S[u]=tot; int pos=tot; for(int i=0;i<=4;i++)ch[pos][i]=dfs(trans(u,i)); return pos; } int main() { scanf("%d",&n); for(int i=1,x;i<=13;i++)scanf("%d%*d",&x),has[x]++; for(int i=0;i<=4;i++) { c[i][0]=1; for(int j=1;j<=i;j++)c[i][j]=c[i-1][j-1]+c[i-1][j]; } fac[0]=inv[0]=inv[1]=1;for(int i=2;i<=4*n;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod; for(int i=1;i<=4*n;i++)fac[i]=1ll*fac[i-1]*i%mod,inv[i]=1ll*inv[i-1]*inv[i]%mod; dfs(node()); f[0][1][0]=1; for(int i=1;i<=n;i++) { memset(f[i&1],0,sizeof f[i&1]); for(int j=1;j<=tot;j++) for(int k=has[i];k<=4;k++) if(ch[j][k]) for(int t=0;t<=(i-1)*4;t++) add(f[i&1][ch[j][k]][k+t],1ll*f[i-1&1][j][t]*c[4-has[i]][k-has[i]]); } for(int i=1,sum;i<=n*4-13;i++) { sum=0; for(int j=1;j<=tot;j++)add(sum,f[n&1][j][i+13]); add(ans,1ll*sum*fac[i]%mod*fac[4*n-13-i]); } ans=(1ll*ans*inv[4*n-13]+1)%mod; printf("%d",ans); }
凸优化DP：https://www.luogu.org/problemnew/show/P3642
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=6e5+100; struct node{int l,r,dis;ll v;}e[N]; int n,m,tot,fa[N],len[N],rt[N],d[N],cnt; ll p[N],sum; int merge(int x,int y) { if(!x||!y)return x+y; if(e[x].v<e[y].v)swap(x,y); e[x].r=merge(e[x].r,y); if(e[e[x].l].dis<e[e[x].r].dis)swap(e[x].l,e[x].r); if(!e[x].r)e[x].dis=0; else e[x].dis=e[e[x].r].dis+1; return x; } int pop(int x){return merge(e[x].l,e[x].r);} int main() { scanf("%d%d",&n,&m); for(int i=2;i<=n+m;i++) { scanf("%d%d",&fa[i],&len[i]); sum+=len[i],d[fa[i]]++; } for(int i=n+m;i>1;i--) { ll l=0,r=0; if(i<=n) { while(--d[i])rt[i]=pop(rt[i]); r=e[rt[i]].v,rt[i]=pop(rt[i]); l=e[rt[i]].v,rt[i]=pop(rt[i]); } e[++tot].v=l+len[i]; e[++tot].v=r+len[i]; rt[i]=merge(rt[i],merge(tot,tot-1)); rt[fa[i]]=merge(rt[fa[i]],rt[i]); } while(d[1]--)rt[1]=pop(rt[1]); while(rt[1])p[++cnt]=e[rt[1]].v,rt[1]=pop(rt[1]); for(int i=1;i<=cnt;i++)sum-=p[i]; printf("%lld",sum); }
插头DP：https://www.luogu.org/problemnew/show/P3190
#include<bits/stdc++.h> using namespace std; const int N=11000,mod=10007; int n,m,ans,p,bin[12],w[110][10],a[2][N],f[2][N],tot[N],hd[N],nxt[N]; void add(int S,int v) { int u=S%mod; for(int i=hd[u];i;i=nxt[i])if(a[p][i]==S){f[p][i]=max(f[p][i],v);return;} a[p][++tot[p]]=S,nxt[tot[p]]=hd[u],hd[u]=tot[p],f[p][tot[p]]=v; } int main() { scanf("%d%d",&n,&m); ans=-1e9; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&w[i][j]); bin[0]=1;for(int i=1;i<=10;i++)bin[i]=bin[i-1]<<2; tot[p]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=tot[p];j++)a[p][j]<<=2; for(int j=1;j<=m;j++) { p^=1; memset(hd,0,sizeof hd); tot[p]=0; for(int k=1;k<=tot[p^1];k++) { int S=a[p^1][k],b1=(S>>j*2-2)%4,b2=(S>>j*2)%4,val=f[p^1][k]; if(!b1&&!b2) { if(i<n&&j<m)add(S+bin[j-1]+2*bin[j],val+w[i][j]); add(S,val); } else if(!b1&&b2) { if(j<m)add(S,val+w[i][j]); if(i<n)add(S-b2*bin[j]+b2*bin[j-1],val+w[i][j]); } else if(b1&&!b2) { if(j<m)add(S-b1*bin[j-1]+b1*bin[j],val+w[i][j]); if(i<n)add(S,val+w[i][j]); } else if(b1==1&&b2==1) { int k1=1; for(int t=j+1;t<=m;++t) { if((S>>t*2)%4==1)k1++; if((S>>t*2)%4==2)k1--; if(!k1){add(S-bin[j-1]-bin[j]-bin[t],val+w[i][j]);break;} } } else if(b1==2&&b2==2) { int k1=1; for(int t=j-2;t>=0;--t) { if((S>>t*2)%4==1)k1--; if((S>>t*2)%4==2)k1++; if(!k1){add(S-2*bin[j-1]-2*bin[j]+bin[t],val+w[i][j]);break;} } } else if(b1==2&&b2==1)add(S-2*bin[j-1]-bin[j],val+w[i][j]); else if(S-bin[j-1]-2*bin[j]==0)ans=max(ans,val+w[i][j]); } } } printf("%d",ans); }
容斥：https://www.lydsy.com/JudgeOnline/problem.php?id=3812
#include<bits/stdc++.h> using namespace std; const int N=65600,mod=1e9+7; int n,m,pw[N],f[N],g[N],h[N],p[N],in[N],ou[N],cnt[N],sz[N]; int main() { scanf("%d%d",&n,&m); pw[0]=1; for(int i=1;i<=m;++i)pw[i]=2ll*pw[i-1]%mod; for(int i=1,x,y;i<=m;++i)scanf("%d%d",&x,&y),in[1<<(--y)]|=1<<(--x),ou[1<<x]|=1<<y; sz[0]=0; for(int i=1;i<(1<<n);++i)sz[i]=sz[i^(i&-i)]+1; for(int S=1;S<(1<<n);++S) { int s=S&-S,T=S^s; h[S]=h[T]+sz[in[s]&T]+sz[ou[s]&T],g[S]=0,f[S]=pw[h[S]]; for(int R=T;R;R=(R-1)&T)g[S]=(g[S]-1ll*g[R]*f[S^R]%mod+mod)%mod; for(int R=S,t;R;R=(R-1)&S) { if(R==S)p[R]=0;else t=(R^S)&-(R^S),p[R]=p[R^t]+sz[ou[t]&R]-sz[in[t]&(R^S)]; f[S]=(f[S]-1ll*pw[p[R]+h[R^S]]*g[R]%mod+mod)%mod; } g[S]=(g[S]+f[S])%mod; } printf("%d",f[(1<<n)-1]); }