【题目描述】

k路归并问题

把k个有序表合并成一个有序表。

元素共有n个。

【输入描述】

读入K。接下来K行。每i行第一个数为Ci表示接下来这一行有Ci个数，表示第i个序列。

总数小于100000。

【输出描述】

【样例输入】

6  3 1 2 3  3 4 5 6  3 7 10 13  3 8 11 14  3 9 12 15  3 0 16 17

【样例输出】

0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17

【题目描述】

每年奶牛们都要举办各种特殊版本的跳房子比赛，包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行，在起点和离起点L远 (1 ≤ L≤ 1,000,000,000) 的终点处均有一个岩石。在起点和终点之间，有N (0 ≤ N ≤ 50,000) 个岩石，每个岩石与起点的距离分别为Di (0 < Di < L)。

在比赛过程中，奶牛轮流从起点出发，尝试到达终点，每一步只能从一个岩石跳到另一个岩石。当然，实力不济的奶牛是没有办法完成目标的。

农夫约翰为他的奶牛们感到自豪并且年年都观看了这项比赛。但随着时间的推移，看着其他农夫的胆小奶牛们在相距很近的岩石之间缓慢前行，他感到非常厌烦。他计划移走一些岩石，使得从起点到终点的过程中，最短的跳跃距离最长。他可以移走除起点和终点外的至多M (0 ≤ M ≤ N) 个岩石。

请帮助约翰确定移走这些岩石后，最长可能的最短跳跃距离是多少？

【输入描述】

第一行包含三个整数L, N, M，相邻两个整数之间用单个空格隔开。

接下来N行，每行一个整数，表示每个岩石与起点的距离。岩石按与起点距离从近到远给出，且不会有两个岩石出现在同一个位置。

【输出描述】

【样例输入】

25 5 2  2  11  14  17  21

【样例输出】

4

【题目描述】

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

(1) 状态定义

• dp[i][j]：表示合并区间 [i, j] 的所有石子堆的最小总代价。

• 初始化：

• 如果 i == j（即区间长度为1），dp[i][j] = 0（因为不需要合并）。

• 否则 dp[i][j] = +∞（初始化为极大值，方便后续取最小值）。

(2) 状态转移方程

• 对于区间 [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] 的石子总重量）。

• 因此，状态转移方程为：

  $$dp[i][j]=\underset{i\le k<j}{\min }(dp[i][k]+dp[k+1][j]+\text{sum}(i,j))$$

(3) 计算顺序

• 按区间长度从小到大计算：

• 先计算所有长度为2的区间，再计算长度为3的区间，依此类推，直到计算整个区间 [0, n-1]。

• 前缀和优化：

• 为了快速计算 sum(i, j)，可以预先计算前缀和数组 prefix：

  $$\text{sum}(i,j)=\text{prefix}[j+1]-\text{prefix}[i]$$

【题目描述】

在某城市里住着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