以下是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 i0; in; i) { cin w; sum w; for (int jsum; j-sum; j--) if (dp[jOFF]) dp[jwOFF] dp[j-wOFF] 1; } int ans 0; for (int i1; isum; i) ans dp[iOFF]; cout ans endl; return 0; }2. 省赛 A 组路径一维 DP / 最短路题意1~2021 点i 可到 i1~i21边权为 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 i1;i2021;i) dp[i]INT_MAX; dp[1]0; for(int i1;i2021;i){ for(int ji1;ji21j2021;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 N100005; vectorint g[N]; int dfs(int u) { int maxh0, cnt0; for(int v:g[u]){ int hdfs(v); maxhmax(maxh,h); cnt; } return maxhcnt; } int main() { int n,fa; cinn; for(int i2;in;i){cinfa; g[fa].push_back(i);} coutdfs(1)endl; return 0; }4. 国赛 B 组最小权值一维 DP题意n 个结点的二叉树权值12w 左 3w 右 左 ²× 右求最小权值。#include iostream #include cstring using namespace std; typedef long long ll; const ll INF1e18; ll dp[2025]; int main() { int n2021; for(int i1;in;i) dp[i]INF; dp[0]0; for(int i1;in;i){ for(int j0;ji;j){ dp[i]min(dp[i], 12*dp[j]3*dp[i-1-j] (ll)j*j*(i-1-j)); } } coutdp[n]endl; return 0; }二、2022 第十三届蓝桥杯 DP 真题1. 省赛 C 组选数异或线性 DP题意求子序列异或和为 x 的方案数。#include iostream using namespace std; const int MOD998244353, N1e510; int dp[N][64],a[N]; int main() { int n,x; cinnx; for(int i0;in;i) cina[i]; dp[0][0]1; dp[0][a[0]]; for(int i1;in;i){ for(int j0;j64;j){ dp[i][j](dp[i-1][j]dp[i-1][j^a[i]])%MOD; } } coutdp[n-1][x]endl; return 0; }2. 省赛 B 组数组切分线性 DP题意数组切分成若干连续段每段 max-minlen-1求方案数。#include iostream #include algorithm using namespace std; const int N10005, MOD1e97; int f[N],a[N],n; int main() { cinn; for(int i1;in;i) cina[i]; f[0]1; for(int i1;in;i){ int mx0,mn1e9; for(int ji;j1;j--){ mxmax(mx,a[j]); mnmin(mn,a[j]); if(mx-mn i-j) f[i](f[i]f[j-1])%MOD; } } coutf[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 i1;i2022;i) for(int j10;j1;j--) for(int ki;k2022;k) dp[j][k]dp[j-1][k-i]; coutdp[10][2022]endl; return 0; }4. 省赛括号序列区间 DP题意合法括号序列方案数。#include iostream #include cstring using namespace std; typedef long long ll; const int N5005, MOD1e97; ll dp[N][N]; char s[N]; int n; int main() { cin(s1); nstrlen(s1); for(int len2;lenn;len){ for(int l1;llen-1n;l){ int rllen-1; if((s[l](||s[l]?)(s[r])||s[r]?)) dp[l][r]dp[l1][r-1](l1r); for(int kl;kr;k) dp[l][r](dp[l][r]dp[l][k]*dp[k1][r])%MOD; } } coutdp[1][n]%MODendl; return 0; }三、2023 第十四届蓝桥杯 DP 真题1. 省赛 B 组接龙数列线性 DP题意数列接龙尾 头求最长长度。#include iostream #include string #include algorithm using namespace std; const int N100005; int f[N][10],n; struct Node{int a,b;}s[N]; int main() { cinn; for(int i1;in;i){ string ss; cinss; s[i].ass[0]-0; s[i].bss.back()-0; } for(int i1;in;i){ for(int j0;j10;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 ans0; for(int j0;j10;j) ansmax(ans,f[n][j]); coutansendl; 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 i1;i2023;i){ string sto_string(i); for(char c:s){ if(c2){ dp[0]; dp[2]dp[1]; } else if(c0) dp[1]dp[0]; else if(c3) dp[3]dp[2]; } } coutdp[3]endl; return 0; }3. 国赛 A 组网络稳定性树形 DP题意树删边保留 k 个关键点连通最小化最大边权。#include iostream #include vector #include algorithm using namespace std; const int N100005; vectorpairint,int g[N]; int d[N],ans-1,n,k; void dfs(int u,int fa){ for(auto [v,w]:g[u]){ if(vfa) continue; dfs(v,u); d[u]d[v]; if(d[v]k) ansmax(ans,w); } } int main() { cinnk; for(int i1;in;i){ int a,b,c; cinabc; g[a].emplace_back(b,c); g[b].emplace_back(a,c); } for(int i0;ik;i){int x; cinx; d[x];} dfs(1,-1); coutansendl; return 0; }四、2024 第十五届蓝桥杯 DP 真题1. 省赛最大子段和变种一维 DP题意最大子段和可翻转一段符号。#include iostream #include algorithm using namespace std; const int N1e55; int a[N],n; // dp0:不翻 dp1:翻中 dp2:已翻 int dp0,dp1,dp2; int main() { cinn; for(int i1;in;i) cina[i]; dp0dp1dp2-1e9; for(int i1;in;i){ int t0dp0, t1dp1, t2dp2; dp0max(a[i], t0a[i]); dp1max(t0-a[i], t1-a[i]); dp2max(t1a[i], t2a[i]); } coutmax({dp0,dp1,dp2})endl; return 0; }2. 国赛砝码称重 II状压 DP题意砝码组合求可称重量数状态压缩。#include iostream #include bitset using namespace std; const int M200000; bitsetM dp; int main() { int n,w,sum0; cinn; dp[0]1; for(int i0;in;i){ cinw; sumw; dp|dpw; } coutdp.count()-1endl; return 0; }3. 省赛节点选择树形 DP题意树选点相邻不选最大权值经典最大独立集。#include iostream #include vector #include algorithm using namespace std; const int N100005; vectorint 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(vfa) continue; dfs(v,u); dp[u][1]dp[v][0]; dp[u][0]max(dp[v][0],dp[v][1]); } } int main() { cinn; for(int i1;in;i) cinval[i]; for(int i1;in;i){ int u,v; cinuv; g[u].push_back(v); g[v].push_back(u); } dfs(1,-1); coutmax(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 N100005; vectorint 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 sum0, mx0; for(int v:g[u]){ if(vfa) continue; dfs(v,u); summax(dp[v][0],dp[v][1]); mxmax(mx, dp[v][1]-dp[v][0]); } dp[u][0]sum; dp[u][1]sumval[u]mx; } int main() { cinn; for(int i1;in;i) cinval[i]; for(int i1;in;i){ int u,v; cinuv; g[u].push_back(v); g[v].push_back(u); } dfs(1,-1); coutmax(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 (mod0!lead); if(dp[pos][mod][limit]!-1) return dp[pos][mod][limit]; int uplimit?a[pos]:9, res0; for(int i0;iup;i){ if(i4) continue; resdfs(pos-1, (mod*10i)%m, limitiup, leadi0); } return dp[pos][mod][limit]res; } int calc(int x){ int len0; while(x) a[len]x%10, x/10; memset(dp,-1,sizeof dp); return dfs(len,0,1,1); } int main() { int l,r; cinlrm; coutcalc(r)-calc(l-1)endl; return 0; }3. 国赛土地整平一维 DP题意最小花费整平土地DP 枚举最优高度。#include iostream #include algorithm #include cmath using namespace std; const int N5005; int a[N],n; long long dp[N][N]; int main() { cinn; for(int i1;in;i) cina[i]; for(int i1;in;i){ long long mn1e18; for(int h0;h5000;h){ mnmin(mn, dp[i-1][h]); dp[i][h]mnabs(a[i]-h); } } long long ans1e18; for(int h0;h5000;h) ansmin(ans,dp[n][h]); coutansendl; return 0; }