【题目描述】
Joe觉得云朵很美，决定去山上的商店买一些云朵。商店里有n朵云，云朵被编号为1，2，…，n，并且每朵云都有一个价值。但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。
但是Joe的钱有限，所以他希望买的价值越多越好。
【输入描述】
第1行n，m，w，表示n朵云，m个搭配，Joe有w的钱。
第2~n+1行，每行ci，di表示i朵云的价钱和价值。
第n+2~n+1+m行，每行ui，vi，表示买ui就必须买vi，同理，如果买vi就必须买ui。
【输出描述】
【样例输入】
5 3 10 3 10 3 10 3 10 5 100 10 1 1 3 3 2 4 2
【样例输出】
1
【数据范围】
30%的数据保证：n≤100；
50%的数据保证：n≤1,000；m≤100；w≤1,000；
100%的数据保证：n≤10,000；0≤m≤5000；w≤10,000。
【题目描述】
某个地区有n(n<=1000)个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为1-n，他们有些团伙之间有直接联系，但是任意两个团伙都可以通过直接或间接的方式联系，这样这里就形成了一个庞大的犯罪集团，犯罪集团的危险程度由集团内的犯罪团伙数量唯一确定，而与单个犯罪团伙的危险程度无关（该犯罪集团的危险程度为n）。现在当地警方希望花尽量少的时间（即打击掉尽量少的团伙），使得庞大的犯罪集团分离成若干个较小的集团，并且他们中最大的一个的危险程度不超过n/2。为达到最好的效果，他们将按顺序打击掉编号1到k的犯罪团伙，请编程求出k的最小值。
【输入描述】
【输出描述】
【样例输入】
7 2 2 5 3 1 3 4 2 2 4 2 2 3 3 1 6 7 2 5 7 2 5 6
【样例输出】
1
一、定义
区间DP是动态规划的一种特殊形式，主要用于解决涉及区间操作的问题，比如合并区间、分割区间、区间匹配等。
其核心思想是通过枚举区间的划分点，将大区间的问题分解为小区间的子问题，逐步求解并保存中间结果。
二、基本特征
问题定义：通常涉及一个序列或区间，如数组、字符串等。
状态表示：一般用 dp[i][j] 表示区间 [i, j] 的最优解。
转移方程：通过枚举区间内的某个分割点 k，将 [i, j] 拆分为 [i, k] 和 [k+1, j]，然后合并子问题的解。
初始化：通常 dp[i][i] 表示单个元素的最优解（如 dp[i][i] = 0 或 dp[i][i] = cost[i]）。
遍历顺序：一般采用区间长度从小到大的顺序计算，确保子问题先被求解。
三、区间DP模板
for (int len = 1; len <= n; len++) { // 枚举区间长度 for (int i = 0; i + len - 1 < n; i++) { // 枚举起点i int j = i + len - 1; // 计算终点j if (len == 1) { // 初始化 dp[i][j] = ...; continue; } for (int k = i; k < j; k++) { // 枚举分割点k dp[i][j] = min/max(dp[i][j], dp[i][k] + dp[k+1][j] + cost); } } }四、例题：石子合并
问题描述：有 n 堆石子排成一排，每次只能合并相邻的两堆，合并的代价是两堆石子的总数。求将所有石子合并成一堆的最小总代价。
输入: stones = [3, 1, 2, 4] 输出: 20 解释: 1. 合并 [1, 2] → 代价=3, 剩余 [3, 3, 4] 2. 合并 [3, 3] → 代价=6, 剩余 [6, 4] 3. 合并 [6, 4] → 代价=10, 总代价=3+6+10=19
dp[i][j]：表示合并区间 [i, j] 的所有石子堆的最小总代价。
初始化：
如果 i == j（即区间长度为1），dp[i][j] = 0（因为不需要合并）。
否则 dp[i][j] = +∞（初始化为极大值，方便后续取最小值）。
对于区间 [i, j]，枚举所有可能的分割点 k（i ≤ k < j），将其分成两个子区间：
[i, k] 和 [k+1, j]。
合并这两个子区间的总代价是：
dp[i][k]（合并 [i, k] 的代价）
dp[k+1][j]（合并 [k+1, j] 的代价）
sum(i, j)（当前合并的代价，即区间 [i, j] 的石子总重量）。
因此，状态转移方程为：
按区间长度从小到大计算：
先计算所有长度为2的区间，再计算长度为3的区间，依此类推，直到计算整个区间 [0, n-1]。
前缀和优化：
为了快速计算 sum(i, j)，可以预先计算前缀和数组 prefix：
【题目描述】
在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：
1、我朋友的朋友是我的朋友；
2、我敌人的敌人是我的朋友；
所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？
【输入描述】
第1行为n和m，1<n<1000,1<=m<=100 000；
以下m行，每行为p x y，p的值为0或1，p为0时，表示x和y是朋友，p为1时，表示x和y是敌人。
【输出描述】
【样例输入】
6 4 1 1 4 0 3 5 0 4 6 1 1 2
【样例输出】
3
【题目描述】
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个算法,计算出将 N 堆石子合并成 1 堆的最小得分和最大得分。
【输入描述】
数据的第 1 行是正整数 N，表示有 N 堆石子。
第 2 行有 N 个整数，第 i个整数ai表示第 i 堆石子的个数。
1≤N≤400，0≤ai≤20。
【输出描述】
输出共2行，第1 行为最小得分，第2 行为最大得分。
【样例输入】
4 4 5 9 4
【样例输出】
43 54
【题目描述】
在一个操场上一排地摆放着N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
设计一个程序，计算出将N堆石子合并成一堆的最小得分。
【输入描述】
第一行为一个正整数N (2≤N≤100)；
以下N行,每行一个正整数，小于10000，分别表示第i堆石子的个数（1≤i≤N）。
【输出描述】
为一个正整数，即最小得分。
【样例输入】
7 13 7 8 16 21 4 18
【样例输出】
239
【题目描述】
给定n个闭区间[ai,bi]，其中i=1,2,...n。任意两个相邻或相交或相邻的闭区间可以合并为一个闭区间。例如，[1,2]和[2,3]可以合并为[1,3]。
[1,3]和[2,4]可以合并为[1,4]，但是[1,2]和[3,4]不可以合并。
我们的任务是判断这些区间是否可以最终合并为一个闭区间，如果可以，则将这个闭区间输出，否则输出no
【输入描述】
第一行为一个整数n，3<n<50000。表示输入区间的数量。
之后n行，在第i行上（1<=i<=n）,为两个整数ai和bi，整数之间用一个空格分隔，表示区间[ai,bi]
(其中1<=ai<=bi<=10000)
【输出描述】
输出一行，如果这些区间最终可以合并为一个闭区间，输出这些闭区间的左右边界，用单个空格隔开；否则输出no
【样例输入】
5 5 6 1 5 10 10 6 9 8 10
【样例输出】
1 10
【题目描述】
设有N个选手进行循环比赛，其中 N=2^M ，要求每名选手要与其他的N-1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。
【输入描述】
输入M
【输出描述】
一个二维数组，表示比赛安排表，一行数据间用一个空格隔开。
【样例输入】
3
【样例输出】
1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1
一、基本思想
归并排序的核心思想是将两个已经有序的子序列合并成一个有序序列。整个过程分为两个主要步骤：
1.分解：将待排序的序列不断二分，直到每个子序列只包含一个元素（此时自然有序）
2.合并：将两个有序的子序列合并为一个有序序列
注意1：若将两个有序表合并成一个有序表，称为2-路归并。
注意2：归并排序则类似于二叉树的后序遍历：它会持续划分区间，直到区间内元素有序，然后利用额外空间对元素进行排序，并将它们合并回原区间，直至整个序列有序。这个过程中，划分区间相当于达到树的最底层，而归并排序则相当于从树的底层开始向上遍历。
二、算法步骤
1.分解阶段：
将长度为n的序列分成两个长度为n/2的子序列
递归地对这两个子序列进行归并排序
直到子序列长度为1（此时已经有序）
2.合并阶段：
申请空间，大小为两个已排序子序列之和
设定两个指针，分别指向两个子序列的起始位置
比较两个指针所指的元素，选择较小的放入合并空间，并移动指针到下一位置
重复上一步直到某一指针超出子序列范围
将另一子序列的剩余元素直接复制到合并序列的末尾
动图如下：
三、时间复杂度
最优情况：O(n log n)
最坏情况：O(n log n)
平均情况：O(n log n)
归并排序的时间复杂度始终是O(n log n)，因为它总是将序列分成两半，需要进行log₂n次分解，每次合并操作的时间复杂度为O(n)。
四、空间复杂度
归并排序需要额外的空间来存储临时合并的数组，因此其空间复杂度为O(n)。
五、稳定性
归并排序是稳定的排序算法，因为在合并过程中，当两个元素相等时，可以保证左边的元素先被放入结果数组中。
六、优缺点
优点：
时间复杂度稳定为O(n log n)
适用于大规模数据排序
稳定排序算法
缺点：
需要额外的存储空间（非原地排序）
对于小规模数据排序效率可能不如简单排序算法
【题目描述】
小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴!因为这些钱还不一定都是你的。接下来主持人宣布了比赛规则:
首先，比赛时间分为n个时段(n≤500)，它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱 wi，wi为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱!
注意:比赛绝对不会让参赛者赔钱!
【输入描述】
第一行为 m，表示一开始奖励给每位参赛者的钱;第二行为n，表示有n个小游戏;
第三行有n个数，分别表示游戏1~n的规定完成期限;第四行有n个数，分别表示游戏1~n不能在规定期限前完成的扣款数
【输出描述】
仅1行。表示小伟能赢取最多的钱,
【样例输入】
10000 7 4 2 4 3 1 4 6 70 60 50 40 30 20 10
【样例输出】
9950