算法竞赛经典题解：分治动态规划与回溯
一、递归分治（2题）
第1题（棋盘覆盖）
题目名称：棋盘覆盖（分治递归）
问题描述：
给定一个棋盘尺寸 $2^k \times 2^k$ （$1 \leq k \leq 6$），棋盘上有一个特殊方格（坐标给定）。请用 L 型骨牌覆盖整个棋盘（特殊方格不覆盖），输出最终的棋盘覆盖方案，用数字表示每个骨牌编号（同一骨牌覆盖的三个格子用同一个正整数编号），特殊方格填-1。
输入格式：
第一行：整数 k
第二行：两个整数 sx, sy 表示特殊方格坐标（0 ≤ sx, sy < 2^k）
输出格式：
$2^k$ 行，每行 $2^k$ 个整数，表示覆盖后的棋盘，每个数占 3 位宽度（右对齐）。
样例输入：
2 0 1样例输出（示意，不唯一）：
2 -1 3 3 2 2 1 3 4 1 1 5 4 4 5 5推荐解法：分治递归填充四个子棋盘。
第2题（合并排序）
题目名称：分治法合并排序
问题描述：
给定一个长度为 N（1 ≤ N ≤ 10^5）的整数数组，请使用分治合并排序递归算法按从小到大排序，并输出排序后的数组。不得使用内置排序函数。
输入格式：
第一行：整数 N
第二行：N 个整数（可能是未排序的）
输出格式：
一行，N 个整数，按从小到大排列，数与数之间用一个空格隔开。
样例输入：
5 3 1 4 1 5样例输出：
1 1 3 4 5#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } int t; for(int i=1;i<=n;i++){ for(int j=1;j<=n-i;j++){ if(a[j]>a[j+1]){ t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } } for(int i=1;i<=n;i++){ cout<<a[i]<<" "; } return 0; }注意：每次递归划分需打印当前 merge 后数组（可选附加分）
二、动态规划（2题）
第3题（矩阵连乘）
题目名称：矩阵连乘最少计算次数
问题描述：
给定 n 个矩阵的尺寸 $p_0, p_1, \dots, p_n$（其中矩阵 $A_i$ 大小为 $p_{i-1} \times p_i$），请使用动态规划求出这些矩阵连乘所需的最少数乘次数，并输出加括号的方案（如(A1(A2A3))）。
输入格式：
第一行：整数 n (1 ≤ n ≤ 100)
第二行：n+1 个整数 $p_0, p_1, ..., p_n$
输出格式：
第一行：最少乘法次数
第二行：最优加括号方案（用括号表示）
样例输入：
3 10 100 5 50样例输出：
7500 (A1(A2A3))第4题（最长公共子序列）
题目名称：最长公共子序列 (LCS)
问题描述：
给定两个字符串 X 和 Y（长度均 ≤ 1000），求它们的最长公共子序列的长度，并输出该子序列本身（若存在多个，输出序号最小的一个，即从左到右第一个找到的）。
输入格式：
第一行：字符串 X
第二行：字符串 Y
输出格式：
第一行：最长公共子序列长度
第二行：该最长公共子序列（若无，输出空行）
样例输入：
ABCBDAB BDCAB样例输出：
4 BCABC++提示：建议使用string类型和二维vector。
三、贪心算法（2题）
第5题（活动安排）
题目名称：活动选择问题
问题描述：
设有 n 个活动（1 ≤ n ≤ 10^4），每个活动给出起始时间 $s_i$ 和结束时间 $f_i$。请用贪心算法（按结束时间最早策略）选出最大数量的互不相容活动，并输出所选活动的序号（原始顺序）。
输入格式：
第一行：整数 n
接下来 n 行：每行两个整数 s_i f_i （s_i < f_i）
输出格式：
第一行：最大活动数量
第二行：所选活动的序号（升序排列，用空格分隔）
样例输入：
5 1 3 2 5 3 6 5 7 6 8样例输出：
3 1 3 5#include<bits/stdc++.h> using namespace std; const int N=1e4+5; struct node{ int start; int end; int idx; }a[N]; bool cmp(node &x,node &y){ return x.end<y.end; } int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i].start>>a[i].end; a[i].idx=i; } sort(a+1,a+n+1,cmp); int last_end=-1; int cnt=0; int b[N];//用于存储选中的活动时间 int b_cnt=0; for(int i=1;i<=n;i++){ if(a[i].start>=last_end){ b[b_cnt++]=a[i].idx; last_end=a[i].end; cnt++; } } cout<<cnt<<endl; for(int i=0;i<b_cnt;i++){ cout<<b[i]; if(i<b_cnt-1)cout<<" "; } return 0; }第6题（哈夫曼编码）
题目名称：哈夫曼树与编码
问题描述：
给定字符集（大小写字母或数字）及其频率，请构建哈夫曼树，并输出每个字符的哈夫曼编码（假设左分支为 '0'，右分支为 '1'）。若有相同频率，按字符 ASCII 码小的优先合并。
输入格式：
第一行：整数 n（2 ≤ n ≤ 26）
接下来 n 行：每行一个字符 c 和一个整数 f（频率）
输出格式：
n 行，每行输出 "字符:编码"，按字符升序排列
样例输入：
5 a 5 b 9 c 12 d 13 e 16样例输出：
a:011 b:10 c:00 d:01 e:11四、回溯法（2题）
第7题（N皇后）
题目名称：N皇后问题解的个数
问题描述：
给定整数 n（1 ≤ n ≤ 15），求解 n 皇后问题有多少种不同的合法摆放方案（任何两个皇后不在同一行、列、对角线）。使用回溯法求解。
输入格式：
一个整数 n
输出格式：
一个整数，表示解的个数
样例输入：
4样例输出：
2提示：可用位运算优化（bitset 或整数位标记）
第8题（0-1背包-回溯法）
题目名称：0-1背包问题（回溯搜索最优解）
问题描述：
给定 n 个物品，每个物品有重量 w_i 和价值 v_i，背包容积为 C。找到最优装载方案的最大总价值。（注：n ≤ 30，C ≤ 10000
输入格式：
第一行：两个整数 n 和 C
第二行：n 个整数 w_1 ... w_n
第三行：n 个整数 v_1 ... v_n
输出格式：
一个整数，最大总价值
样例输入：
4 7 2 3 4 5 3 4 5 6样例输出：
9#include<bits/stdc++.h> using namespace std; const int N=1e4+5; const int M=30; int dp[M][N]; int a[N],b[N]; int main(){ int n,c; cin>>n>>c; for(int i=1;i<=n;i++){ cin>>a[i]; cin>>b[i]; } for(int i=0;i<=n;i++){ dp[i][0]=0; } for(int j=0;j<=c;j++){ dp[0][j]=0; } for(int i=1;i<=n;i++){ for(int j=1;j<=c;j++){ if(a[i]>j){ dp[i][j]=dp[i-1][j]; } else{ dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]]+b[i]); } } } cout<<dp[n][c]<<endl; return 0; }五、分支限界法（1题）
第9题（单源最短路径）
题目名称：分支限界法求单源最短路径
问题描述：
给定带权有向图 G（顶点数 n ≤ 1000，边数 m ≤ 10000，权重非负），源点编号为 0。请用计算从源点到所有其他顶点的最短路径长度。
输入格式：
第一行：两个整数 n m
接下来 m 行：每行三个整数 u v w（表示 u→v 的有向边，权 w）
最后一行：源点编号 s（默认 0）
输出格式：
一行，n 个整数，dist[0] ... dist[n-1]（从 s 出发到各点距离，不可达输出 -1）
样例输入：
5 8 0 1 10 0 2 5 1 2 2 1 3 1 2 1 3 2 3 9 2 4 2 3 4 4样例输出：
0 8 5 9 7六、综合（1题）
第10题（双船装载 + 回溯）
题目名称：双船装载可行性判断
问题描述：
有 n 个集装箱（1 ≤ n ≤ 20）需装到两艘载重分别为 c1 和 c2 的轮船上，第 i 个集装箱重量 w_i。试用回溯法判断是否存在一种装载方案将所有集装箱装完，并输出其中一艘船的装载方案（船1）。
输入格式：
第一行：三个整数 n c1 c2
第二行：n 个整数 w_1 ... w_n （所有重量之和 ≤ c1+c2）
输出格式：
第一行："YES" 或 "NO"
若 YES，第二行输出船1所装集装箱的序号（1-based，升序，用空格分隔）
样例输入：
5 10 10 4 3 5 2 6样例输出：
YES 1 2 4