石子合并最大值在端点取到的证明
时间: 2023-05-29 22:03:34 浏览: 84
假设有一种合并方法,使得最大值在端点没有取到。
设原始的石子序列为 A,合并后的序列为 B。
因为最大值没有取到,所以合并后的序列 B 中存在一个位置 i,使得 A[i] 和 A[i+1] 合并后的值小于 B[i]。
我们可以将 B[i] 拆分成 A[i] 和 A[i+1] 的和,即 B[i] = A[i] + A[i+1] + x,其中 x 为在 A[i] 和 A[i+1] 之间插入的石子数。
假设我们将 A[i] 和 A[i+1] 合并成一个数后,得到的新的序列为 C。则 C 的第 i 个数为 A[i]+A[i+1],第 i-1 个数为 B[i-1]-A[i+1]-x,第 i+1 个数为 B[i+1]-A[i]-x。
我们可以发现,将 A[i] 和 A[i+1] 合并后,序列的最大值不会变小。因为 A[i] 和 A[i+1] 的和必须大于等于 B[i],而新的序列 C 的第 i 个数为 A[i]+A[i+1],必然大于等于 B[i]。
同时,我们可以发现,将 A[i] 和 A[i+1] 合并后,新的序列 C 和原始序列 A 的差值不会变大。因为新的序列 C 和原始序列 A 仅仅是在 i 和 i+1 的位置上发生了变化,其他位置的数值都没有改变。而 C[i]+C[i+1]-A[i]-A[i+1] = x,即新插入的石子数,不会让差值变大。
因此,我们可以通过将 A[i] 和 A[i+1] 合并,得到一个新的序列 C,使得 C 的最大值和原始序列 A 的最大值相等,且最大值在端点取到。这与假设不符,证明了原命题。
相关问题
石子合并问题c语言最大最小值
石子合并问题是一个经典的动态规划问题,可以用C语言来解决。具体实现方法如下:
1. 定义一个数组dp,表示合并第i个到第j个石子所需的最小代价。
2. 初始化dp数组,将所有dp[i][i]设为0,因为合并一个石子不需要代价。
3. 遍历石子合并的区间长度len,从2开始到n,n为石子的数量。在每个长度下再遍历区间起点i,从1开始到n-len+1。
4. 对于每个区间起点i,计算其终点j=i+len-1。然后遍历所有可能的分割点k,从i开始到j-1。将区间[i, k]和区间[k+1, j]合并,并计算合并的代价。
5. 选取合并代价最小的分割点k,并更新dp[i][j]的值。即dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1],其中sum[i]表示石子的前缀和,用于快速计算区间和。
6. 遍历完所有区间长度和起点后,dp[1][n]即为合并所有石子的最小代价。同时可以记录每个dp[i][j]的最小值和最大值,用于输出。
下面是C语言的实现代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAXN 1005
#define INF INT_MAX
int n;
int a[MAXN], sum[MAXN];
int dp[MAXN][MAXN], min_dp[MAXN][MAXN], max_dp[MAXN][MAXN];
int min(int a, int b) {
return a < b ? a : b;
}
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
sum[i] = sum[i-1] + a[i];
}
for (int i = 1; i <= n; i++) {
dp[i][i] = 0;
min_dp[i][i] = a[i];
max_dp[i][i] = a[i];
}
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= n-len+1; i++) {
int j = i + len - 1;
min_dp[i][j] = INF;
max_dp[i][j] = 0;
for (int k = i; k < j; k++) {
dp[i][j] = dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1];
min_dp[i][j] = min(min_dp[i][j], dp[i][j]);
max_dp[i][j] = max(max_dp[i][j], dp[i][j]);
}
}
}
printf("%d %d\n", min_dp[1][n], max_dp[1][n]);
return 0;
}
```
输入格式:第一行是石子的数量n,接下来一行是n个整数,表示每个石子的价值。
输出格式:一行,包括合并所有石子的最小代价和最大代价。
样例输入:
```
5
1 2 3 4 5
```
样例输出:
```
33 55
```
时间复杂度:O(n^3)。空间复杂度:O(n^2)。
动态规划石子合并子问题计算最优值
石子合并问题是一个经典的动态规划问题,可以使用DP来解决。假设有一个长度为n的数组a,表示有n堆石子,第i堆石子有a[i]个。现在要将这n堆石子合并成一堆石子,每次只能合并相邻的两堆石子,合并两堆石子的代价为这两堆石子的石子数之和。求将n堆石子合并成一堆石子的最小代价。
我们可以定义一个二维数组dp,其中dp[i][j]表示合并第i堆到第j堆石子的最小代价。显然,当i=j时,dp[i][j]=0,因为只有一堆石子,无需合并。当i<j时,dp[i][j]的值可以通过以下递推公式计算:
dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum(a[i...j])), i<=k<j
其中sum(a[i...j])表示第i堆到第j堆石子的石子数之和。
根据这个递推公式,我们可以使用二重循环来计算dp数组的值。具体地,外层循环枚举子问题的规模,从小到大依次计算dp[i][j],内层循环枚举子问题的起点k,计算dp[i][j]的值。
下面是一个简单的Python代码实现:
```python
def merge_stones(n, a):
dp = [[0] * n for _ in range(n)]
for k in range(2, n+1):
for i in range(n-k+1):
j = i + k - 1
dp[i][j] = float('inf')
for m in range(i, j):
dp[i][j] = min(dp[i][j], dp[i][m] + dp[m+1][j] + sum(a[i:j+1]))
return dp[0][n-1]
```
这个算法的时间复杂度为O(n^3),空间复杂度为O(n^2),可以通过此方法计算石子合并子问题的最优值。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)