登录
← 返回首页 | 代码片段 › 5 动态规划 › 动态规划 / 搜索
JSON MD

5 动态规划

含 36 个代码片段
二进制优化多重背包 宝物筛选 5.5.1 DP优化
29 行
CPP JSON
【二进制优化多重背包(宝物筛选)】 DP 优化模板,利用数据结构或数学性质加速状态转移。 核心函数: void in(Re &x) — 核心算法函数 关键配置: N=103,M=4e4+3 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 28 行 CPP
#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);
}
单调队列优化多重背包 CodeVS 5429 5.5.1 DP优化
29 行
CPP JSON
【单调队列优化多重背包(CodeVS 5429)】 单调队列优化 DP 模板,滑动窗口维护转移最值。 核心函数: void in(Re &x) — 核心算法函数 int max(Re a,Re b) — 核心算法函数 int min(Re a,Re b) — 核心算法函数 关键配置: N=7003,M=7003 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 28 行 CPP
#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]);
}
最长公共子序列 二分 5.5.1 DP优化
33 行
CPP JSON
luogu-judger-enable-o2
C++ 32 行 CPP
// luogu-judger-enable-o2
#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];
    for(i=1;i<=n;i++)printf("%d ",b[i]);puts("");
    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]);
    	}
    }
    for(i=1;i<=n;i++)printf("%d ",f[i]);puts("");
    printf("%d",len);
    return 0;
}
基站选址 线段树优化 5.5.1 DP优化
96 行
CPP JSON
【基站选址(线段树优化)】 DP 优化模板,利用数据结构或数学性质加速状态转移。 核心函数: void in(Re &x) — 核心算法函数 LL calc(Re j,Re i) — 计算函数 void updata(Re p,LL v) — 核心算法函数 void pushdown(Re p) — 下传懒标记 void build(Re p,Re L,Re R) — 构建数据结构(建树/建图) void change(Re p,Re L,Re R,Re l,Re r,Re v) — 核心算法函数 void change(Re p,Re L,Re R,Re x,Re v) — 核心算法函数 LL ask(Re p,Re L,Re R,Re l,Re r) — 核心算法函数 核心结构体:Segment_Tree 复杂度:时间复杂度取决于状态数和转移复杂度 说明:freopen("123.txt","r",stdin); 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 95 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define LL long long
#define Re register int
using namespace std;
const LL N=2e4+3,inf=1e18;
int n,K,L[N],R[N],D[N],C[N],W[N],S[N];LL ans=inf,dp[N];vector<int>V[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 LL calc(Re j,Re i){
	LL ans=0;
	for(Re k=j+1;k<i;++k)if(L[k]>j&&R[k]<i)ans+=W[k];
	return ans;
}
struct Segment_Tree{
	#define pl (p<<1)
	#define pr (p<<1|1)
	#define mid ((L+R)>>1)
	LL tr[N<<2],add[N<<2];
	inline void updata(Re p,LL v){tr[p]+=v,add[p]+=v;}
	inline void pushdown(Re p){
		if(add[p])updata(pl,add[p]),updata(pr,add[p]),add[p]=0;
	}
	inline void build(Re p,Re L,Re R){
		add[p]=0;
		if(L==R){tr[p]=dp[L];return;}
		build(pl,L,mid),build(pr,mid+1,R);
		tr[p]=min(tr[pl],tr[pr]);
	}
	inline void change(Re p,Re L,Re R,Re l,Re r,Re v){
		if(l<=L&&R<=r){updata(p,v);return;}
		pushdown(p);
		if(l<=mid)change(pl,L,mid,l,r,v);
		if(r>mid)change(pr,mid+1,R,l,r,v);
		tr[p]=min(tr[pl],tr[pr]);
	}
	inline void change(Re p,Re L,Re R,Re x,Re v){
		if(L==R){tr[p]+=v;return;}
		pushdown(p);
		if(x<=mid)change(pl,L,mid,x,v);
		else change(pr,mid+1,R,x,v);
		tr[p]=min(tr[pl],tr[pr]);
	}
	inline LL ask(Re p,Re L,Re R,Re l,Re r){
		if(l<=L&&R<=r)return tr[p];
		LL ans=inf;pushdown(p);
		if(l<=mid)ans=min(ans,ask(pl,L,mid,l,r));
		if(r>mid)ans=min(ans,ask(pr,mid+1,R,l,r));
		return ans; 
	}
	#undef mid
}TR;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(K);
	for(Re i=2;i<=n;++i)in(D[i]);
	for(Re i=1;i<=n;++i)in(C[i]);
	for(Re i=1;i<=n;++i){
		in(S[i]);
		Re l=1,r=i;
		while(l<r){
			Re mid=l+r>>1;
			if(D[mid]>=D[i]-S[i])r=mid;
			else l=mid+1;
		}
		L[i]=r;
		l=i,r=n;
		while(l<r){
			Re mid=l+r+1>>1;
			if(D[mid]<=D[i]+S[i])l=mid;
			else r=mid-1;
		}
		R[i]=l,V[R[i]].push_back(i);
	}
	for(Re i=1;i<=n;++i)in(W[i]);
	memset(dp,20,sizeof(dp));
	dp[0]=0,D[0]=-1e9,C[n+1]=0;
	for(Re k=1;k<=K;++k){
		TR.build(1,0,n);
		for(Re i=1;i<=n+1;++i){
			LL tmp=dp[i];
			dp[i]=min(dp[i],TR.ask(1,0,n,0,i-1)+C[i]);
			for(Re j=0,SZ=V[i].size();j<SZ;++j)TR.change(1,0,n,0,L[V[i][j]]-1,W[V[i][j]]);
			if(dp[i]!=tmp)TR.change(1,0,n,i,dp[i]-tmp);
		}
		ans=min(ans,dp[n+1]);
	}
	printf("%lld\n",ans);
}
Yet Another Minimization Problem 分治套莫队 5.5.1 DP优化
41 行
CPP JSON
【Yet Another Minimization Problem(分治套莫队)】 DP 优化模板,利用数据结构或数学性质加速状态转移。 核心函数: void in(Re &x) — 核心算法函数 LL calc(Re L,Re R) — 计算函数 void sakura(Re l,Re r,Re L,Re R,Re k) — 后缀数组 核心结构体:MODUI 关键配置: N=1e5+3,M=23 复杂度:时间复杂度取决于状态数和转移复杂度 说明:freopen("123.txt","r",stdin); 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 40 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,M=23;
int n,K,A[N];LL dp[M][N];
inline void in(Re &x){
	int f=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=f?-x:x;
}
struct MODUI{
	int nowL,nowR,cnt[N];LL ans;
	inline LL calc(Re L,Re R){
		while(nowR<R)++nowR,ans+=cnt[A[nowR]]++;
		while(nowL>L)--nowL,ans+=cnt[A[nowL]]++;
		while(nowR>R)ans-=--cnt[A[nowR]],--nowR;
		while(nowL<L)ans-=--cnt[A[nowL]],++nowL;
		return ans;
	}
}TR;
inline void sakura(Re l,Re r,Re L,Re R,Re k){
	if(l>r)return;Re mid=l+r>>1,w=0;LL tmp;
	for(Re j=L;j<=R&&j<mid;++j)
		if((tmp=dp[k-1][j]+TR.calc(j+1,mid))<=dp[k][mid])
			dp[k][mid]=tmp,w=j;
	sakura(l,mid-1,L,w,k),sakura(mid+1,r,w,R,k);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(K);
	for(Re i=1;i<=n;++i)in(A[i]);
	memset(dp,19,sizeof(dp)),dp[0][0]=0;
	TR.nowL=1,TR.nowR=0;
	for(Re k=1;k<=K;++k)sakura(k,n,k-1,n-1,k);
	printf("%lld\n",dp[K][n]);
}
[P5574]任务分配问题 分治套莫队套树状数组 5.5.1 DP优化
43 行
CPP JSON
【[P5574]任务分配问题(分治套莫队套树状数组)】 DP 优化模板,利用数据结构或数学性质加速状态转移。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re v) — 加法更新 int ask(Re x) — 核心算法函数 LL calc(Re L,Re R) — 计算函数 void sakura(Re l,Re r,Re L,Re R,Re k) — 后缀数组 核心结构体:BIT 关键配置: N=25003,M=27 复杂度:时间复杂度取决于状态数和转移复杂度 说明:freopen("123.txt","r",stdin); 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 42 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=25003,M=27;
int n,K,A[N];LL dp[M][N];
inline void in(Re &x){
	int f=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=f?-x:x;
}
struct BIT{
	int nowL,nowR,C[N];LL ans;
	inline void add(Re x,Re v){if(!x)return;while(x<=n)C[x]+=v,x+=x&-x;}
	inline int ask(Re x){Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
	inline LL calc(Re L,Re R){
		while(nowR<R)++nowR,ans+=ask(A[nowR]-1),add(A[nowR],1);
		while(nowL>L)--nowL,ans+=nowR-nowL-ask(A[nowL]),add(A[nowL],1);
		while(nowR>R)add(A[nowR],-1),ans-=ask(A[nowR]-1),--nowR;
		while(nowL<L)add(A[nowL],-1),ans-=nowR-nowL-ask(A[nowL]),++nowL;
		return ans;
	}
}TR;
inline void sakura(Re l,Re r,Re L,Re R,Re k){
	if(l>r)return;Re mid=l+r>>1,w=0;LL tmp;
	for(Re j=L;j<=R&&j<mid;++j)
		if((tmp=dp[k-1][j]+TR.calc(j+1,mid))<=dp[k][mid])
			dp[k][mid]=tmp,w=j;
	sakura(l,mid-1,L,w,k),sakura(mid+1,r,w,R,k);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(K);
	for(Re i=1;i<=n;++i)in(A[i]);
	memset(dp,19,sizeof(dp)),dp[0][0]=0;
	TR.nowL=1,TR.nowR=0;
	for(Re k=1;k<=K;++k)sakura(k,n,k-1,n-1,k);
	printf("%lld\n",dp[K][n]);
}
Lightning Conductor 二分栈 5.5.1 DP优化
45 行
CPP JSON
【Lightning Conductor(二分栈)】 DP 优化模板,利用数据结构或数学性质加速状态转移。 核心函数: void in(Re &x) — 核心算法函数 double Y(Re i,Re j) — 核心算法函数 int find_Poi(int j1,int j2) — 查找(并查集寻根/二分查找) void sakura(无参数) — 后缀数组 关键配置: N=5e5+3 复杂度:时间复杂度取决于状态数和转移复杂度 说明:当前位置i使用直线j1的值小于直线j2的值,说明交点i在当前位置右侧,因此右边界要缩小;找到位置j使得直线Q[j]与直线Q[j+1]的交点大于i;��ôֱ��Q[j]����iǰ�����������ֱ�ߣ����𰸣��Լ�����ͼģ��һ�¾Ͷ��� 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 44 行 CPP
#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){
    	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]);
}
Lightning Conductor 分治 5.5.1 DP优化
31 行
CPP JSON
【Lightning Conductor(分治)】 DP 优化模板,利用数据结构或数学性质加速状态转移。 核心函数: void in(Re &x) — 核心算法函数 void sakura(Re l,Re r,Re L,Re R) — 后缀数组 关键配置: N=5e5+3 复杂度:时间复杂度取决于状态数和转移复杂度 说明:������p[i]�����ž��ߵ�j0��������ߵ�j��������j<=i�����˴���j<=mid 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 30 行 CPP
#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)
		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]);
}
Cats Transport min 5.5.1 DP优化
36 行
CPP JSON
【Cats Transport】 DP 优化模板,利用数据结构或数学性质加速状态转移。 核心函数: LL min(Re a,Re b) — 核心算法函数 LL X(Re j) — 核心算法函数 LL Y(Re j) — 核心算法函数 long double slope(Re i,Re j) — 核心算法函数 关键配置: N=1e5+5 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 35 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register LL
const int N=1e5+5;
LL p,n,m,P,w,h,t,H[N],T[N],Q[N],S[N],dp[105][N];
inline LL min(Re a,Re b){return a<b?a:b;}
//                         i
//                         k=j+1
//dp[p][i]=dp[p-1][j]+(i-j)*T[i]-(S[i]-S[j])
//(T[i]) * j + (dp[p][i]-i*T[i]+S[i]) = (dp[p-1][j]+S[j])
//  k    * x +            b           =        y
inline LL X(Re j){return j;}
inline LL Y(Re j){return dp[p-1][j]+S[j];}
inline long double slope(Re i,Re j){return (long double)(Y(j)-Y(i))/(X(j)-X(i));}
int main(){
	memset(dp,0x3f,sizeof(dp));dp[0][0]=0;
    scanf("%lld%lld%lld",&n,&m,&P);
    for(Re i=2;i<=n;H[i]+=H[i-1],++i)scanf("%lld",&H[i]);
    for(Re i=1;i<=m;T[i]=t-H[w],++i)scanf("%lld%lld",&w,&t);
    std::sort(T+1,T+m+1);
    for(Re i=1;i<=m;++i)S[i]=S[i-1]+T[i];
    for(p=1;p<=P;++p){
    	h=1,t=0,Q[++t]=0,dp[p][0]=0;
	    for(Re i=1;i<=m;++i){
	        while(h<t&&slope(Q[h],Q[h+1])<=T[i])++h;
	        dp[p][i]=min(dp[p-1][i],dp[p-1][j=Q[h]]+(i-j)*T[i]-S[i]+S[j]);
	        if(Y(i)>=0x3f3f3f3f3f3f3f3fll)continue;
			while(h<t&&slope(Q[t-1],Q[t])>=slope(Q[t-1],i))--t;
	        Q[++t]=i;
	    }
	}
    printf("%lld",dp[P][m]); 
}
CDQ 斜率优化 (k x均不单调) Building Bridges 5.5.1 DP优化
60 行
CPP JSON
【CDQ 斜率优化 (k x均不单调)(Building Bridges)】 斜率优化 DP 模板,维护凸包将转移复杂度降至 O(N)/O(N log N)。 核心函数: void in(Re &x) — 核心算法函数 bool cmp(QAQ A,QAQ B) — 核心算法函数 LD slope(Re i,Re j) — 核心算法函数 void CDQ(Re L,Re R) — 核心算法函数 核心结构体:QAQ 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 59 行 CPP
#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]);
}
二分 斜率优化 (x单调 k不单调) 任务安排3 5.5.1 DP优化
38 行
CPP JSON
【二分 斜率优化 (x单调 k不单调)(任务安排3)】 斜率优化 DP 模板,维护凸包将转移复杂度降至 O(N)/O(N log N)。 核心函数: LL min(Re a,Re b) — 核心算法函数 LL X(Re j) — 核心算法函数 LL Y(Re j) — 核心算法函数 long double slope(Re i,Re j) — 核心算法函数 LL sakura(Re k) — 后缀数组 关键配置: N=3e5+5 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 37 行 CPP
#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]是单调递增
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));}
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;
		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;
        Q[++t]=i;
	}
    printf("%lld",dp[n]);
}
单调队列 斜率优化 (x k 均单调) 玩具装箱 Toy 5.5.1 DP优化
26 行
CPP JSON
【单调队列 斜率优化 (x k 均单调)(玩具装箱 Toy)】 斜率优化 DP 模板,维护凸包将转移复杂度降至 O(N)/O(N log N)。 核心函数: LL min(Re a,Re b) — 核心算法函数 LL X(Re j) — 核心算法函数 LL Y(Re j) — 核心算法函数 long double slope(Re i,Re j) — 核心算法函数 关键配置: N=5e4+5 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 25 行 CPP
#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];
//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));}
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;
        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;
        Q[++t]=i;
    }
    printf("%lld",dp[n]);
}
仓库建设 min 5.5.1 DP优化
26 行
CPP JSON
【仓库建设】 DP 优化模板,利用数据结构或数学性质加速状态转移。 核心函数: LL min(Re a,Re b) — 核心算法函数 LL X(Re j) — 核心算法函数 LL Y(Re j) — 核心算法函数 long double slope(Re i,Re j) — 核心算法函数 关键配置: N=1e6+5 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 25 行 CPP
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register LL
const int N=1e6+5;
LL i,j,n,w,h=1,t=0,W[N],P[N],C[N],Q[N],SP[N],SC[N],dp[N];
inline LL min(Re a,Re b){return a<b?a:b;}
//dp[i]=dp[j]+Ci+Wi*(SP[i]-SP[j])-(SC[i]-SC[j])
//(Wi) * SP[j] + (dp[i]+SC[i]-Wi*SP[i]) = (dp[j]+SC[j])
// k   *   x   +           b            =       y
inline LL X(Re j){return SP[j];}
inline LL Y(Re j){return dp[j]+SC[j];}
inline long double slope(Re i,Re j){return (long double)(Y(j)-Y(i))/(X(j)-X(i));}
int main(){
    scanf("%lld",&n);
    for(i=1;i<=n;SC[i]=SC[i-1]+W[i]*SP[i],SP[i]+=SP[i-1],++i)scanf("%lld%lld%lld",&W[i],&SP[i],&C[i]);
    Q[++t]=0;
    for(i=1;i<=n;++i){
        while(h<t&&slope(Q[h],Q[h+1])<W[i])++h;
        dp[i]=dp[j=Q[h]]+C[i]+W[i]*(SP[i]-SP[j])-SC[i]+SC[j];
        while(h<t&&slope(Q[t-1],Q[t])>slope(Q[t-1],i))--t;
        Q[++t]=i;
    }
    printf("%lld",dp[n]);
}
任务安排1 O n^2 5.5.1 DP优化
19 行
CPP JSON
【任务安排1 O(n^2)】 DP 优化模板,利用数据结构或数学性质加速状态转移。 核心函数: LL min(Re a,Re b) — 核心算法函数 关键配置: N=1e4+5 复杂度:时间复杂度取决于状态数和转移复杂度 说明:dp[p][i]=min(dp[p-1][j]+(ST[i]+S*p)*(SF[i]-SF[j]));;dp[i]=min(dp[i],dp[j]+ST[i]*(SF[i]-SF[j])+S*(SF[n]-SF[j])); 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 18 行 CPP
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register LL
const int N=1e4+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]=min(dp[i],dp[j]+ST[i]*(SF[i]-SF[j])+S*(SF[n]-SF[j]));
inline LL min(Re a,Re b){return a<b?a:b;}
int main(){
    memset(dp,127,sizeof(dp));dp[0]=0;
    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]);
    for(i=1;i<=n;++i)
    	for(j=0;j<i;++j)
    		dp[i]=min(dp[i],dp[j]+ST[i]*(SF[i]-SF[j])+S*(SF[n]-SF[j]));
    printf("%lld",dp[n]);
}
任务安排2 O n 5.5.1 DP优化
27 行
CPP JSON
【任务安排2 O(n)】 DP 优化模板,利用数据结构或数学性质加速状态转移。 核心函数: LL min(Re a,Re b) — 核心算法函数 LL X(Re j) — 核心算法函数 LL Y(Re j) — 核心算法函数 long double slope(Re i,Re j) — 核心算法函数 关键配置: N=3e5+5 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 26 行 CPP
#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
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 (long double)(Y(j)-Y(i))/(X(j)-X(i));}
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){
		while(h<t&&slope(Q[h],Q[h+1])<(S+ST[i]))++h;
        dp[i]=dp[j=Q[h]]+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;
        Q[++t]=i;
	}
    printf("%lld",dp[n]);
}
土地征用 Land Acquisition min 5.5.1 DP优化
30 行
CPP JSON
【土地征用 Land Acquisition】 DP 优化模板,利用数据结构或数学性质加速状态转移。 核心函数: LL min(Re a,Re b) — 核心算法函数 LL X(Re j) — 核心算法函数 LL Y(Re j) — 核心算法函数 long double slope(Re i,Re j) — 核心算法函数 核心结构体:QAQ 关键配置: N=5e4+5 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 29 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register LL
const int N=5e4+5;
struct QAQ{LL L,W;inline bool operator<(QAQ p)const{return W<p.W;}}a[N];
LL i,j,n,m,h=1,t=0,H=1,T,L[N],W[N],Q[N],dp[N];
inline LL min(Re a,Re b){return a<b?a:b;}
inline LL X(Re j){return -L[j+1];}
inline LL Y(Re j){return dp[j];}
inline long double slope(Re i,Re j){return (long double)(Y(j)-Y(i))/(X(j)-X(i));}
int main(){
    scanf("%lld",&m);
    for(i=1;i<=m;++i)scanf("%lld%lld",&a[i].L,&a[i].W);
    std::sort(a+1,a+m+1);
    for(i=1;i<=m;++i){
    	while(1<=n&&L[n]<=a[i].L)--n;
    	L[++n]=a[i].L,W[n]=a[i].W;
	}
    Q[++t]=0;
    for(i=1;i<=n;++i){
        while(h<t&&slope(Q[h],Q[h+1])<W[i])++h;
        dp[i]=dp[j=Q[h]]+L[j+1]*W[i];
        while(h<t&&slope(Q[t-1],Q[t])>slope(Q[t-1],i))--t;
        Q[++t]=i;
    }
    printf("%lld",dp[n]);
}
序列分割 max 5.5.1 DP优化
29 行
CPP JSON
【序列分割】 DP 优化模板,利用数据结构或数学性质加速状态转移。 核心函数: LL max(Re a,Re b) — 核心算法函数 LL X(Re j) — 核心算法函数 LL Y(Re j) — 核心算法函数 long double slope(Re i,Re j) — 核心算法函数 关键配置: N=1e5+5,M=205 复杂度:时间复杂度取决于状态数和转移复杂度 说明:dp[p][i]=dp[p-1][j]+S[j]*(S[i]-S[j]);(S[i]) * S[j] + (-dp[p][i]) = (S[j]^2-dp[p-1][j]);k * x + b = y 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 28 行 CPP
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register LL
const int N=1e5+5,M=205;
LL tmp,i,j,p,n,K,h,t,Q[N],S[N],to[M][N],dp[M][N];
inline LL max(Re a,Re b){return a>b?a:b;}
//dp[p][i]=dp[p-1][j]+S[j]*(S[i]-S[j])
//(S[i]) * S[j] + (-dp[p][i]) = (S[j]^2-dp[p-1][j])
//  k    *  x   +       b     =          y
inline LL X(Re j){return S[j];}
inline LL Y(Re j){return S[j]*S[j]-dp[p-1][j];}
inline long double slope(Re i,Re j){return X(j)==X(i)?-1e18:(long double)(Y(j)-Y(i))/(X(j)-X(i));}
int main(){
    scanf("%lld%lld",&n,&K);
    for(i=1;i<=n;S[i]+=S[i-1],++i)scanf("%lld",&S[i]);
    for(p=1;p<=K;++p){
        h=1,t=0,Q[++t]=p-1;
        for(i=p;i+K-p<=n;++i){
            while(h<t&&slope(Q[h],Q[h+1])<S[i])++h;
        	dp[p][i]=dp[p-1][to[p][i]=j=Q[h]]+S[j]*(S[i]-S[j]);
       		while(h<t&&slope(Q[t-1],Q[t])>slope(Q[t-1],i))--t;
        	Q[++t]=i;
        }
    }
    printf("%lld\n",dp[K][n]);
    for(i=n,j=K;j>=1;--j)printf("%lld ",i=to[j][i]);
}
征途 min 5.5.1 DP优化
35 行
CPP JSON
【征途】 DP 优化模板,利用数据结构或数学性质加速状态转移。 核心函数: LL min(Re a,Re b) — 核心算法函数 LL X(Re j) — 核心算法函数 LL Y(Re j) — 核心算法函数 long double slope(Re i,Re j) — 核心算法函数 关键配置: N=3e3+5 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 34 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register LL
const int N=3e3+5;
LL p,i,j,n,m,h,t,Q[N],S[N],dp[N][N];
//S_walk[m]=S[n]
//              m                               m
//             i=1                             i=1
//        m
//       i=1
//dp[p][i]=min(dp[p-1][j]+(S[i]-S[j])^2)
//(2*S[i]) * S[j] + (dp[p][i]-S[i]^2) = (dp[p-1][j]+S[j]^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[p-1][j]+S[j]*S[j];}
inline long double slope(Re i,Re j){return (long double)(Y(j)-Y(i))/(X(j)-X(i));}
int main(){
    memset(dp,127,sizeof(dp));dp[0][0]=0;
    scanf("%lld%lld",&n,&m);
    for(i=1;i<=n;S[i]+=S[i-1],++i)scanf("%lld",&S[i]);
    for(p=1;p<=m;++p){
    	h=1,t=0,Q[++t]=0,dp[p][0]=0;
	    for(i=1;i<=n;++i){
	        while(h<t&&slope(Q[h],Q[h+1])<2*S[i])++h;
	        dp[p][i]=min(dp[p-1][i],dp[p-1][j=Q[h]]+(S[i]-S[j])*(S[i]-S[j]));
			while(h<t&&slope(Q[t-1],Q[t])>slope(Q[t-1],i))--t;
	        Q[++t]=i;
	    }
	}
    printf("%lld",m*dp[m][n]-S[n]*S[n]);
}
摆渡车 min 5.5.1 DP优化
29 行
CPP JSON
【摆渡车】 DP 优化模板,利用数据结构或数学性质加速状态转移。 核心函数: int min(Re a,Re b) — 核心算法函数 int X(Re j) — 核心算法函数 int Y(Re j) — 核心算法函数 long double slope(Re i,Re j) — 核心算法函数 关键配置: N=4e6+105 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 28 行 CPP
#include<cstdio>
#define Re register int
const int N=4e6+105;
int i,j,n,m,h=1,t=0,T,ti,ans=2e9,G[N],S[N],Q[N],dp[N];
inline int min(Re a,Re b){return a<b?a:b;}
//                 i
//                 k=j+1
//dp[i]=dp[j]+(G[i]-G[j])*i-(S[i]-S[j])
//(i) * G[j] + (dp[i]+S[j]-i*G[i]) = (dp[j]+S[j])
// k  *  x   +          b          =      y
inline int X(Re j){return G[j];}
inline int Y(Re j){return dp[j]+S[j];}
inline long double slope(Re i,Re j){return X(i)==X(j)?(Y(j)>Y(i)?2e9:-2e9):(long double)(Y(j)-Y(i))/(long double)(X(j)-X(i));}
int main(){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;T=-min(-T,-ti),++G[ti],S[ti]+=ti,++i)scanf("%d",&ti);
    for(i=1;i<T+m;++i)G[i]+=G[i-1],S[i]+=S[i-1];
    for(i=0;i<m;++i)dp[i]=G[i]*i-S[i];
    Q[++t]=0;
    for(i=m;i<T+m;++i){
    	while(h<t&&slope(Q[h],Q[h+1])<=i)++h;
        dp[i]=dp[j=Q[h]]+(G[i]-G[j])*i-S[i]+S[j];
       	while(h<t&&slope(Q[t-1],Q[t])>=slope(Q[t-1],i-m+1))--t;
        Q[++t]=i-m+1;//(j+1)+m<=i
	}
    for(i=T;i<T+m;++i)ans=min(ans,dp[i]);
    printf("%d",ans);
}
特别行动队 max 5.5.1 DP优化
26 行
CPP JSON
【特别行动队】 DP 优化模板,利用数据结构或数学性质加速状态转移。 核心函数: LL max(Re a,Re b) — 核心算法函数 LL X(Re j) — 核心算法函数 LL Y(Re j) — 核心算法函数 long double slope(Re i,Re j) — 核心算法函数 关键配置: N=1e6+5 复杂度:时间复杂度取决于状态数和转移复杂度 说明:dp[i]=dp[j]+a*(S[i]-S[j])^2+b*(S[i]-S[j])+c;(-2a*S[i]) * S[j] + (b*S[i]+a*S[i]^2-dp[i]) = (b*S[j]-dp[j]-a*S[j]^2);k * x + b = y 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 25 行 CPP
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register LL
const int N=1e6+5;
LL tmp,i,j,n,a,b,c,h=1,t=0,Q[N],S[N],dp[N];
inline LL max(Re a,Re b){return a>b?a:b;}
//dp[i]=dp[j]+a*(S[i]-S[j])^2+b*(S[i]-S[j])+c
//(-2a*S[i]) * S[j] + (b*S[i]+a*S[i]^2-dp[i]) = (b*S[j]-dp[j]-a*S[j]^2)
//    k      * x    +           b             =             y
inline LL X(Re j){return S[j];}
inline LL Y(Re j){return b*S[j]-dp[j]-a*S[j]*S[j];}
inline long double slope(Re i,Re j){return (long double)(Y(j)-Y(i))/(X(j)-X(i));}
int main(){
	scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
	for(i=1;i<=n;S[i]+=S[i-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*a*S[i]))++h;
		dp[i]=dp[j=Q[h]]+a*(S[i]-S[j])*(S[i]-S[j])+b*(S[i]-S[j])+c;
		while(h<t&&slope(Q[t-1],Q[t])>slope(Q[t-1],i))--t;
		Q[++t]=i;
	}
	printf("%lld",dp[n]);
}
货币兑换 CDQ斜率优化 5.5.1 DP优化
75 行
CPP JSON
【货币兑换(CDQ斜率优化)】 DP 优化模板,利用数据结构或数学性质加速状态转移。 核心函数: int dcmp(LD a) — 核心算法函数 void in(Re &x) — 核心算法函数 void in(LD &X) — 核心算法函数 bool cmp(QAQ A,QAQ B) — 核心算法函数 LD slope(Re i,Re j) — 核心算法函数 void CDQ(Re L,Re R) — 核心算法函数 核心结构体:QAQ 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 74 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define LD long double
#define Re register int
using namespace std;
const LL N=1e5+3,inf=1e18;
const LD eps=1e-20;
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}
int n,h,t,Q[N];LD S,A[N],B[N],Ra[N],f[N],dp[N];
inline void in(Re &x){
    int dp=0;x=0;char c=getchar();
    while(c<'0'||c>'9')dp|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=dp?-x:x;
}
inline void in(LD &X){
	X=0;LD Y=1.0;int dp=0;char c=getchar();
	while(c<'0'||c>'9')dp|=c=='-',c=getchar(); 
	while(c>='0'&&c<='9')X=X*10+(c^48),c=getchar(); 
	if(c=='.'){c=getchar();while(c>='0'&&c<='9')X+=(Y/=10)*(c^48),c=getchar();}
	X=dp?-X:X;
}
//dp[i]=max((B[i]/A[i])*f[j]+Ra[j]*f[j]),f[i]=dp[i]/(A[i]*Ra[i]+B[i])
//(B[i]/A[i])*f[j]+(-dp[i])=(-Ra[j]*f[j])
//     k     * x  +   b    =     y
#define X(i) (a[i].x)
#define Y(i) (a[i].y)
struct QAQ{
	LD k,x,y;int id;
	inline bool operator<(const QAQ &O)const{return dcmp(x-O.x)?x<O.x:y<O.y;}
}a[N],b[N];
inline bool cmp(QAQ A,QAQ B){return dcmp(A.k-B.k)<0;}
inline LD slope(Re i,Re j){return X(i)==X(j)?(Y(j)>Y(i)?inf:-inf):(Y(j)-Y(i))/(X(j)-X(i));}
inline void CDQ(Re L,Re R){
	if(L==R){
		Re j=a[L].id;
//		printf("getdp(%d), dp=%.3Lf\n",j,dp[j]);
		if(j>1)dp[j]=max(dp[j-1],A[j]*dp[j]),f[j]=dp[j]/(A[j]*Ra[j]+B[j]);
		a[L].x=f[j],a[L].y=-Ra[j]*f[j];
//		printf("k=%.3Lf, x=%.3Lf, y=%.3Lf\n",a[L].k,a[L].x,a[L].y);
		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]=max(dp[id],-(a[j].y-a[i].k*a[j].x));
	}
	CDQ(mid+1,R);Re p=L-1;p1=L,p2=mid+1;
	while(p1<=mid&&p2<=R)b[++p]=a[p1]<a[p2]?a[p1++]:a[p2++];
	while(p1<=mid)b[++p]=a[p1++];while(p2<=R)b[++p]=a[p2++];
	for(Re i=L;i<=R;++i)a[i]=b[i];
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(S);
	for(Re i=1;i<=n;++i)in(A[i]),in(B[i]),in(Ra[i]),dp[i]=-inf;
	for(Re i=1;i<=n;++i)a[i].k=B[i]/A[i],a[i].id=i;
	f[1]=(dp[1]=S)/(A[1]*Ra[1]+B[1]);
//	for(Re i=2;i<=n;++i){
//		for(Re j=1;j<i;++j)dp[i]=max(dp[i],f[j]*Ra[j]+f[j]*B[i]/A[i]);
//		dp[i]=max(dp[i-1],A[i]*dp[i]),f[i]=dp[i]/(A[i]*Ra[i]+B[i]);
//	}
	sort(a+1,a+n+1,cmp),CDQ(1,n);
	printf("%.3Lf",dp[n]);
}
锯木厂选址 X 5.5.1 DP优化
39 行
CPP JSON
【锯木厂选址】 DP 优化模板,利用数据结构或数学性质加速状态转移。 核心函数: void in(Re &x) — 核心算法函数 LL X(Re j) — 核心算法函数 LL Y(Re j) — 核心算法函数 LD slope(Re i,Re j) — 核心算法函数 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 38 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LD long double
#define LL long long
#define Re register int
using namespace std;
const LL N=2e5+3,inf=1e18;
int n,x,h=1,t,Q[N];LL ans=inf,Ans,D[N],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;
}
// S严格递增
// D严格递减
//F[j]=max(D[i]*S[i]-D[i]*S[j]+D[j]*S[j])
//D[i]*S[j] + F[i]-D[i]*S[i] = D[j]*S[j]
// k  * x   +       b        =     y
inline LL X(Re j){return S[j];}
inline LL Y(Re j){return D[j]*S[j];}
inline LD slope(Re i,Re j){return (LD)(Y(j)-Y(i))/(X(j)-X(i));}
int main(){
//	freopen("123.txt","r",stdin);
	in(n);
	for(Re i=1;i<=n;++i)in(x),S[i]=S[i-1]+x,in(x),D[i+1]=D[i]+x;
	for(Re i=1;i<=n+1;++i)D[i]=D[n+1]-D[i],Ans+=D[i]*(S[i]-S[i-1]);
	for(Re i=1;i<=n;++i){
		LL tmp=-inf;
		while(h<t&&slope(Q[h],Q[h+1])>=D[i])++h;
		if(h<=t)ans=min(ans,Ans-(D[i]*(S[i]-S[Q[h]])+D[Q[h]]*S[Q[h]]));
		while(h<t&&slope(Q[t-1],i)>=slope(Q[t-1],Q[t]))--t;
		Q[++t]=i;
//		for(Re j=1;j<i;++j)tmp=max(tmp,D[i]*(S[i]-S[j])+D[j]*S[j]);
	}
	printf("%lld\n",ans);
}
高速公路 x单调 k不单调,树上转移 5.5.1 DP优化
54 行
CPP JSON
【高速公路(x单调 k不单调,树上转移)】 DP 优化模板,利用数据结构或数学性质加速状态转移。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 LL Y(Re j) — 核心算法函数 LL X(Re j) — 核心算法函数 LD slope(Re i,Re j) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 核心结构体:QAQ 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:加速DP转移,将O(N²)优化至O(N)/O(N log N)
C++ 53 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const LL N=1e6+3,inf=4e18;
int n,m,x,y,z,o,h,t,P[N],Q[N],A[N],Fa[N],head[N];LL ans,dp[N],dis[N];
struct QAQ{int w,to,next;}a[N];
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;
}
//dp[i]=min(dp[j]+P[i]*(dis[i]-dis[j])+A[i])
//dp[i]=dp[j]+P[i]*dis[i]-P[i]*dis[j]+A[i]
//P[i]*dis[j]+dp[i]-P[i]*dis[i]-A[i]=dp[j]
//  k *  x   +          b           =  y
inline LL Y(Re j){return dp[j];}
inline LL X(Re j){return dis[j];}
inline LD slope(Re i,Re j){return (LD)(Y(j)-Y(i))/(X(j)-X(i));}
inline void dfs(Re x,Re fa){
	dp[x]=inf;Re h0=h,t0=t;
	Re l=h,r=t;
	while(l<r){
		Re mid=l+r>>1;
		if(slope(Q[mid],Q[mid+1])<=P[x])l=mid+1;
		else r=mid;
	}
	h=r;
	dp[x]=dp[Q[h]]+(LL)P[x]*(dis[x]-dis[Q[h]])+A[x];
	l=h,r=t;
	while(l<r){
		Re mid=l+r+1>>1;
		if(slope(Q[mid-1],x)<=slope(Q[mid-1],Q[mid]))r=mid-1;
		else l=mid;
	}
	Re Qx0=Q[r+1];t=r,Q[++t]=x;
	for(Re i=head[x],to;i;i=a[i].next)dis[to=a[i].to]=dis[x]+a[i].w,dfs(to,x);
	h=h0,Q[t]=Qx0,t=t0;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n);
	for(Re i=2;i<=n;++i)in(x),in(z),in(P[i]),in(A[i]),add(x,i,z),Fa[i]=x;
	dp[1]=0,h=1,t=0,Q[++t]=1;
	for(Re i=head[1],to;i;i=a[i].next)
		dis[to=a[i].to]=dis[1]+a[i].w,dfs(to,1);
	for(Re i=2;i<=n;++i)printf("%lld\n",dp[i]);
}
01背包 采药 5.5.2 背包问题
14 行
CPP JSON
【01背包(采药)】 01背包的算法实现模板。 适用场景:资源分配问题、物品选取的最优方案
C++ 13 行 CPP
#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]);
    return 0;
}
二维费用 找啊找啊找GF 5.5.2 背包问题
20 行
CPP JSON
【二维费用(找啊找啊找GF)】 二维费用的算法实现模板。 适用场景:资源分配问题、物品选取的最优方案
C++ 19 行 CPP
#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]);
}
分组背包 金明的预算方案 5.5.2 背包问题
22 行
CPP JSON
【分组背包(金明的预算方案)】 分组背包的算法实现模板。 适用场景:资源分配问题、物品选取的最优方案
C++ 21 行 CPP
#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]);
}
多人背包 kth_knapsack 5.5.2 背包问题
23 行
CPP JSON
【多人背包】 多人背包的算法实现模板。 适用场景:资源分配问题、物品选取的最优方案
C++ 22 行 CPP
#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);
    return 0;
}
多重背包 (宝物筛选) 二进制优化 5.5.2 背包问题
29 行
CPP JSON
【多重背包 (宝物筛选)(二进制优化)】 代码包含 in 等核心函数,实现了 多重背包 (宝物筛选) 的算法逻辑。 核心函数: void in(Re &x) — 核心算法函数 关键配置: N=103,M=4e4+3 适用场景:资源分配问题、物品选取的最优方案
C++ 28 行 CPP
#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);
}
完全背包 货币系统 5.5.2 背包问题
17 行
CPP JSON
【完全背包(货币系统)】 完全背包的算法实现模板。 适用场景:资源分配问题、物品选取的最优方案
C++ 16 行 CPP
#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);
	}
}
混合背包 樱花 5.5.2 背包问题
25 行
CPP JSON
【混合背包(樱花)】 混合背包的算法实现模板。 适用场景:资源分配问题、物品选取的最优方案
C++ 24 行 CPP
#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]);
	return 0;
}
数位DP (Windy数) dfs 5.5.3 数位DP
27 行
CPP JSON
【数位DP (Windy数)(dfs)】 数位 DP 模板,在数字的十进制/二进制位上做记忆化搜索。 核心函数: int dfs(int len,int up,int ok) — 深度优先搜索遍历 int sovle(int x) — 核心算法函数 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:与数字各位有关的计数/最优化问题
C++ 26 行 CPP
#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));
}
数位DP (Windy数) dp 5.5.3 数位DP
37 行
CPP JSON
【数位DP (Windy数)(dp)】 数位 DP 模板,在数字的十进制/二进制位上做记忆化搜索。 核心函数: int dpp(int len) — 核心算法函数 int sovle(int x) — 核心算法函数 int sakura(无参数) — 后缀数组 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:与数字各位有关的计数/最优化问题
C++ 36 行 CPP
#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 Eat the Trees 5.5.4 插头DP
46 行
CPP JSON
【插头DP(Eat the Trees)】 插头 DP(Plug DP / 轮廓线 DP)模板,用于网格路径覆盖问题。 核心函数: void in(Re &x) — 核心算法函数 关键配置: N=15,M=8192+3 复杂度:时间复杂度取决于状态数和转移复杂度 说明:freopen("123.txt","r",stdin); 适用场景:网格上的路径覆盖/回路计数问题(如哈密顿回路、多米诺覆盖)
C++ 45 行 CPP
#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]);
	}
}
插头DP (括号表示法) 单回路 5.5.4 插头DP
60 行
CPP JSON
【插头DP (括号表示法)(单回路)】 插头 DP(Plug DP / 轮廓线 DP)模板,用于网格路径覆盖问题。 核心函数: void in(Re &x) — 核心算法函数 关键配置: N=14,M=1594323+3 复杂度:时间复杂度取决于状态数和转移复杂度 说明:freopen("123.txt","r",stdin);;printf("edx=%d, edy=%d\n",edx,edy); 适用场景:网格上的路径覆盖/回路计数问题(如哈密顿回路、多米诺覆盖)
C++ 59 行 CPP
#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;}
					}
				}
				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;}
					}
				}
				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);
}
插头DP (括号表示法+优化状态枚举) 单回路 5.5.4 插头DP
70 行
CPP JSON
【插头DP (括号表示法+优化状态枚举)(单回路)】 插头 DP(Plug DP / 轮廓线 DP)模板,用于网格路径覆盖问题。 核心函数: void in(Re &x) — 核心算法函数 void add(Re s,LL v) — 加法更新 void CL(无参数) — 核心算法函数 关键配置: N=14,M=1594323+3 复杂度:时间复杂度取决于状态数和转移复杂度 说明:freopen("123.txt","r",stdin);;printf("edx=%d, edy=%d\n",edx,edy); 适用场景:网格上的路径覆盖/回路计数问题(如哈密顿回路、多米诺覆盖)
C++ 69 行 CPP
#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;}
					}
				}
				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;}
					}
				}
				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);
}
地板 三进制插头dp 5.5.4 插头DP
77 行
CPP JSON
【地板(三进制插头dp)】 插头 DP(Plug DP / 轮廓线 DP)模板,用于网格路径覆盖问题。 核心函数: void in(Re &x) — 核心算法函数 void mo(Re &x) — 核心算法函数 关键配置: N=103,M=177147+3,P=20110520 复杂度:时间复杂度取决于状态数和转移复杂度 说明:freopen("123.txt","r",stdin); 适用场景:网格上的路径覆盖/回路计数问题(如哈密顿回路、多米诺覆盖)
C++ 76 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=103,M=177147+3,P=20110520;
int n,m,o,V,Mi[N],A[N][N],A_[N][N],dp[2][M];char s[N];//0:没有插头 1:还没完成的插头 2:已经完成的插头
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 mo(Re &x){if(x>P)x-=P;}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m);
	for(Re i=1;i<=n;++i){
		scanf("%s",s+1);
		for(Re j=1;j<=m;++j)A[i][j]=(s[j]=='*');
	}
	if(n<m){
		for(Re i=1;i<=n;++i)
			for(Re j=1;j<=m;++j)
				A_[j][i]=A[i][j];
		swap(n,m);
		for(Re i=1;i<=n;++i)
			for(Re j=1;j<=m;++j)
				A[i][j]=A_[i][j];
	}
	Mi[0]=1;for(Re i=1;i<=m+1;++i)Mi[i]=Mi[i-1]*3;
	V=Mi[m+1]-1,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,ML=Mi[j-1],MU=Mi[j+1-1];
				if(A[i][j]){
					if(!L&&!U)mo(dp[o][s]+=dp[o^1][s]);
				}
				else{
					if(L==0&&U==0){
						mo(dp[o][s+ML]+=dp[o^1][s]);
						mo(dp[o][s+MU]+=dp[o^1][s]);
						mo(dp[o][s+2*ML+2*MU]+=dp[o^1][s]);
					}
					if(L==0&&U==1){
						mo(dp[o][s+MU]+=dp[o^1][s]);
						mo(dp[o][s+ML-MU]+=dp[o^1][s]);
					}
					if(L==0&&U==2){
						mo(dp[o][s+2*ML-2*MU]+=dp[o^1][s]);
						mo(dp[o][s-2*MU]+=dp[o^1][s]);
					}
					if(L==1&&U==0){
						mo(dp[o][s+ML]+=dp[o^1][s]);
						mo(dp[o][s-ML+MU]+=dp[o^1][s]);
					}
					if(L==1&&U==1)mo(dp[o][s-ML-MU]+=dp[o^1][s]);
					if(L==1&&U==2);
					if(L==2&&U==0){
						mo(dp[o][s-2*ML+2*MU]+=dp[o^1][s]);
						mo(dp[o][s-2*ML]+=dp[o^1][s]);
					}
					if(L==2&&U==1);
					if(L==2&&U==2);
				}
			}
		}
	}
	printf("%d\n",dp[o][0]);
}
已复制