当前位置：首页 > news >正文

速成蓝桥杯之DP（三）

news 2026/5/7 4:31:28

以下是2021–2025 年蓝桥杯 C++ 组所有 DP 类真题（省赛 + 国赛）+ 完整可运行 C++ 代码 + 简要题解，按年份分类整理。

一、2021 第十二届蓝桥杯 DP 真题

1. 省赛 AB 组：砝码称重（01 背包方案数）

题意：n 个砝码，可放左 / 右盘，求能称出多少种不同重量。思路：01 背包，偏移量处理负数。

#include <iostream> #include <cstring> using namespace std; const int OFF = 100000; bool dp[200005]; int main() { int n, sum = 0, w; cin >> n; memset(dp, 0, sizeof dp); dp[OFF] = 1; // 0重量 for (int i=0; i<n; i++) { cin >> w; sum += w; for (int j=sum; j>=-sum; j--) if (dp[j+OFF]) dp[j+w+OFF] = dp[j-w+OFF] = 1; } int ans = 0; for (int i=1; i<=sum; i++) ans += dp[i+OFF]; cout << ans << endl; return 0; }

2. 省赛 A 组：路径（一维 DP / 最短路）

题意：1~2021 点，i 可到 i+1~i+21，边权为 LCM (i,j)，求 1→2021 最短路。

#include <iostream> #include <climits> #include <algorithm> using namespace std; int gcd(int a,int b){return b?gcd(b,a%b):a;} int lcm(int a,int b){return a/gcd(a,b)*b;} int dp[2022]; int main() { for(int i=1;i<=2021;i++) dp[i]=INT_MAX; dp[1]=0; for(int i=1;i<=2021;i++){ for(int j=i+1;j<=i+21&&j<=2021;j++){ if(dp[i]!=INT_MAX) dp[j]=min(dp[j], dp[i]+lcm(i,j)); } } cout << dp[2021] << endl; return 0; }

3. 省赛 A 组：左孩子右兄弟（树形 DP）

题意：多叉树转左孩子右兄弟，求最大深度。

#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N=100005; vector<int> g[N]; int dfs(int u) { int maxh=0, cnt=0; for(int v:g[u]){ int h=dfs(v); maxh=max(maxh,h); cnt++; } return maxh+cnt; } int main() { int n,fa; cin>>n; for(int i=2;i<=n;i++){cin>>fa; g[fa].push_back(i);} cout<<dfs(1)<<endl; return 0; }

4. 国赛 B 组：最小权值（一维 DP）

题意：n 个结点的二叉树，权值：1+2w 左 + 3w 右 + 左 ²× 右，求最小权值。

#include <iostream> #include <cstring> using namespace std; typedef long long ll; const ll INF=1e18; ll dp[2025]; int main() { int n=2021; for(int i=1;i<=n;i++) dp[i]=INF; dp[0]=0; for(int i=1;i<=n;i++){ for(int j=0;j<i;j++){ dp[i]=min(dp[i], 1+2*dp[j]+3*dp[i-1-j] + (ll)j*j*(i-1-j)); } } cout<<dp[n]<<endl; return 0; }

二、2022 第十三届蓝桥杯 DP 真题

1. 省赛 C 组：选数异或（线性 DP）

题意：求子序列异或和为 x 的方案数。

#include <iostream> using namespace std; const int MOD=998244353, N=1e5+10; int dp[N][64],a[N]; int main() { int n,x; cin>>n>>x; for(int i=0;i<n;i++) cin>>a[i]; dp[0][0]=1; dp[0][a[0]]++; for(int i=1;i<n;i++){ for(int j=0;j<64;j++){ dp[i][j]=(dp[i-1][j]+dp[i-1][j^a[i]])%MOD; } } cout<<dp[n-1][x]<<endl; return 0; }

2. 省赛 B 组：数组切分（线性 DP）

题意：数组切分成若干连续段，每段 max-min=len-1，求方案数。

#include <iostream> #include <algorithm> using namespace std; const int N=10005, MOD=1e9+7; int f[N],a[N],n; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; f[0]=1; for(int i=1;i<=n;i++){ int mx=0,mn=1e9; for(int j=i;j>=1;j--){ mx=max(mx,a[j]); mn=min(mn,a[j]); if(mx-mn == i-j) f[i]=(f[i]+f[j-1])%MOD; } } cout<<f[n]<<endl; return 0; }

3. 国赛 B 组：2022（多维背包）

题意：选 10 个不同正整数和为 2022，求方案数。

#include <iostream> using namespace std; typedef long long LL; LL dp[11][2025]; int main() { dp[0][0]=1; for(int i=1;i<=2022;i++) for(int j=10;j>=1;j--) for(int k=i;k<=2022;k++) dp[j][k]+=dp[j-1][k-i]; cout<<dp[10][2022]<<endl; return 0; }

4. 省赛：括号序列（区间 DP）

题意：合法括号序列方案数。

#include <iostream> #include <cstring> using namespace std; typedef long long ll; const int N=5005, MOD=1e9+7; ll dp[N][N]; char s[N]; int n; int main() { cin>>(s+1); n=strlen(s+1); for(int len=2;len<=n;len++){ for(int l=1;l+len-1<=n;l++){ int r=l+len-1; if((s[l]=='('||s[l]=='?')&&(s[r]==')'||s[r]=='?')) dp[l][r]+=dp[l+1][r-1]+(l+1==r); for(int k=l;k<r;k++) dp[l][r]=(dp[l][r]+dp[l][k]*dp[k+1][r])%MOD; } } cout<<dp[1][n]%MOD<<endl; return 0; }

三、2023 第十四届蓝桥杯 DP 真题

1. 省赛 B 组：接龙数列（线性 DP）

题意：数列接龙（尾 = 头），求最长长度。

#include <iostream> #include <string> #include <algorithm> using namespace std; const int N=100005; int f[N][10],n; struct Node{int a,b;}s[N]; int main() { cin>>n; for(int i=1;i<=n;i++){ string ss; cin>>ss; s[i].a=ss[0]-'0'; s[i].b=ss.back()-'0'; } for(int i=1;i<=n;i++){ for(int j=0;j<10;j++) f[i][j]=f[i-1][j]; f[i][s[i].b]=max(f[i][s[i].b], f[i-1][s[i].a]+1); } int ans=0; for(int j=0;j<10;j++) ans=max(ans,f[n][j]); cout<<ans<<endl; return 0; }

2. 省赛：子 2023（线性 DP）

题意：拼接 1~2023，求子序列 "2023" 个数。

#include <iostream> #include <string> using namespace std; typedef long long ll; ll dp[4]; // 0:2,1:20,2:202,3:2023 int main() { for(int i=1;i<=2023;i++){ string s=to_string(i); for(char c:s){ if(c=='2'){ dp[0]++; dp[2]+=dp[1]; } else if(c=='0') dp[1]+=dp[0]; else if(c=='3') dp[3]+=dp[2]; } } cout<<dp[3]<<endl; return 0; }

3. 国赛 A 组：网络稳定性（树形 DP）

题意：树删边，保留 k 个关键点连通，最小化最大边权。

#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N=100005; vector<pair<int,int>> g[N]; int d[N],ans=-1,n,k; void dfs(int u,int fa){ for(auto [v,w]:g[u]){ if(v==fa) continue; dfs(v,u); d[u]+=d[v]; if(d[v]==k) ans=max(ans,w); } } int main() { cin>>n>>k; for(int i=1;i<n;i++){ int a,b,c; cin>>a>>b>>c; g[a].emplace_back(b,c); g[b].emplace_back(a,c); } for(int i=0;i<k;i++){int x; cin>>x; d[x]++;} dfs(1,-1); cout<<ans<<endl; return 0; }

四、2024 第十五届蓝桥杯 DP 真题

1. 省赛：最大子段和变种（一维 DP）

题意：最大子段和，可翻转一段符号。

#include <iostream> #include <algorithm> using namespace std; const int N=1e5+5; int a[N],n; // dp0:不翻 dp1:翻中 dp2:已翻 int dp0,dp1,dp2; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; dp0=dp1=dp2=-1e9; for(int i=1;i<=n;i++){ int t0=dp0, t1=dp1, t2=dp2; dp0=max(a[i], t0+a[i]); dp1=max(t0-a[i], t1-a[i]); dp2=max(t1+a[i], t2+a[i]); } cout<<max({dp0,dp1,dp2})<<endl; return 0; }

2. 国赛：砝码称重 II（状压 DP）

题意：砝码组合，求可称重量数（状态压缩）。

#include <iostream> #include <bitset> using namespace std; const int M=200000; bitset<M> dp; int main() { int n,w,sum=0; cin>>n; dp[0]=1; for(int i=0;i<n;i++){ cin>>w; sum+=w; dp|=dp<<w; } cout<<dp.count()-1<<endl; return 0; }

3. 省赛：节点选择（树形 DP）

题意：树选点，相邻不选，最大权值（经典最大独立集）。

#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N=100005; vector<int> g[N]; int val[N],dp[N][2],n; void dfs(int u,int fa){ dp[u][1]=val[u]; dp[u][0]=0; for(int v:g[u]){ if(v==fa) continue; dfs(v,u); dp[u][1]+=dp[v][0]; dp[u][0]+=max(dp[v][0],dp[v][1]); } } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>val[i]; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } dfs(1,-1); cout<<max(dp[1][0],dp[1][1])<<endl; return 0; }

五、2025 第十六届蓝桥杯 DP 真题

1. 省赛 G：生产车间（树形 DP）

题意：树选生产线，收益最大化，依赖约束。

#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N=100005; vector<int> g[N]; int val[N],dp[N][2],n; void dfs(int u,int fa){ dp[u][1]=val[u]; dp[u][0]=0; int sum=0, mx=0; for(int v:g[u]){ if(v==fa) continue; dfs(v,u); sum+=max(dp[v][0],dp[v][1]); mx=max(mx, dp[v][1]-dp[v][0]); } dp[u][0]=sum; dp[u][1]=sum+val[u]+mx; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>val[i]; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } dfs(1,-1); cout<<max(dp[1][0],dp[1][1])<<endl; return 0; }

2. 省赛：数位倍数（数位 DP）

题意：[L,R] 中是 m 倍数且不含 4 的数的个数。

#include <iostream> #include <cstring> using namespace std; int a[20],m,dp[20][1005][2]; int dfs(int pos,int mod,bool limit,bool lead){ if(!pos) return (mod==0&&!lead); if(dp[pos][mod][limit]!=-1) return dp[pos][mod][limit]; int up=limit?a[pos]:9, res=0; for(int i=0;i<=up;i++){ if(i==4) continue; res+=dfs(pos-1, (mod*10+i)%m, limit&&i==up, lead&&i==0); } return dp[pos][mod][limit]=res; } int calc(int x){ int len=0; while(x) a[++len]=x%10, x/=10; memset(dp,-1,sizeof dp); return dfs(len,0,1,1); } int main() { int l,r; cin>>l>>r>>m; cout<<calc(r)-calc(l-1)<<endl; return 0; }

3. 国赛：土地整平（一维 DP）

题意：最小花费整平土地，DP 枚举最优高度。

#include <iostream> #include <algorithm> #include <cmath> using namespace std; const int N=5005; int a[N],n; long long dp[N][N]; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){ long long mn=1e18; for(int h=0;h<=5000;h++){ mn=min(mn, dp[i-1][h]); dp[i][h]=mn+abs(a[i]-h); } } long long ans=1e18; for(int h=0;h<=5000;h++) ans=min(ans,dp[n][h]); cout<<ans<<endl; return 0; }

查看全文

http://www.jsqmd.com/news/767905/