动态规划三元组最小距离 用动态规划求解

动态规划三元组最小距离问题通常涉及在一个序列或数组中找到三个元素，使得它们之间的最小差值最大化。这个问题可以看作是一个优化版本的三点选择问题。给定一个整数数组 `nums` 和长度 `n`，我们想要找出三个不同的索引 `i`, `j`, `k`，使得 `|nums[i] - nums[j]| + |nums[j] - nums[k]| + |nums[i] - nums[k]|` 最小。

解决此问题的一个常见算法是使用动态规划的二维状态数组，通常命名为 dp。我们可以设置两个状态：

1. dp[i][0] 表示在前 i 个元素中找到的最大差值，其中没有包含第 i 个元素。
2. dp[i][1] 表示在前 i 个元素中找到的最大差值，其中包含了第 i 个元素。

初始化dp数组时，dp[0][0] = dp[0][1] = 0，因为只有一个元素时，最大差值就是该元素本身。

然后，对于每个索引 `i`，从 `1` 到 `n-2`，我们更新这两个状态：

- dp[i][0] = max(dp[i-1][0], dp[i-1][1] - nums[i])
- dp[i][1] = max(dp[i-1][0] + nums[i], dp[i-1][1])

最后，dp[n-2][0] 就是最小的三元组差值。这个过程利用了子问题重叠的性质，避免了重复计算。

相关问题

用C语言 已知含有n个顶点的带权连通无向图，采用邻接矩阵存储，邻接矩阵以三元组的形式给出，只给出不包括主对角线元素在内的下三角形部分的元素，且不包括不相邻的顶点对。求该连通图的最小生成树的权值

这个问题可以使用 Prim 或 Kruskal 算法求解，我们以 Prim 算法为例。

Prim 算法的基本思想是从一个顶点出发，不断扩展最小生成树，每次找到与当前最小生成树相邻的边中权值最小的边，将其加入最小生成树中，直到所有顶点都被加入最小生成树为止。

具体实现时，我们可以用一个数组记录每个顶点是否已经被加入最小生成树，以及到当前最小生成树的最短距离，然后每次选择未加入最小生成树且到当前最小生成树距离最短的顶点加入最小生成树，并更新其他顶点到最小生成树的距离。

以下是用 C 语言实现 Prim 算法的代码：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAXN 1000 // 最大顶点数
#define INF INT_MAX // 无穷大

int n; // 顶点数
int w[MAXN][MAXN]; // 邻接矩阵
int d[MAXN]; // 到最小生成树的距离
int vis[MAXN]; // 是否已加入最小生成树

int prim() {
    int i, j, k;
    int sum = 0;
    for (i = 1; i < n; i++) {
        d[i] = w[0][i];
        vis[i] = 0;
    }
    vis[0] = 1;
    for (i = 1; i < n; i++) {
        int min = INF, u;
        for (j = 0; j < n; j++) {
            if (!vis[j] && d[j] < min) {
                min = d[j];
                u = j;
            }
        }
        vis[u] = 1;
        sum += min;
        for (k = 0; k < n; k++) {
            if (!vis[k] && w[u][k] < d[k]) {
                d[k] = w[u][k];
            }
        }
    }
    return sum;
}

int main() {
    int i, j;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        for (j = 0; j <= i; j++) {
            scanf("%d", &w[i][j]);
            w[j][i] = w[i][j]; // 填充上三角
        }
    }
    int ans = prim();
    printf("%d\n", ans);
    return 0;
}

这段代码输入包括顶点数和下三角形部分的邻接矩阵，输出最小生成树的权值。注意这里我们填充了上三角，使得邻接矩阵变成了完整的矩阵。

最小生成树（普里姆算法）pta

### 关于最小生成树普里姆算法的PTA平台练习题解法

#### 题目描述
假设在一个无向连通图中存在多个节点以及连接这些节点的不同权重的边。目标是从这个图中选出一些边构成一棵树，使得这棵树包含所有的节点，并且所选边的总权重尽可能小。

#### 解决方案概述
为了求解此类问题，在PTA平台上可以采用普里姆算法解决最小生成树(MST)问题。此方法基于贪心策略，逐步构建MST直到覆盖所有给定图形中的顶点[^1]。

#### 实现细节
对于具体实现而言，通常会初始化一个集合用于存储当前已加入到MST里的顶点；另外还需要维护一个数组记录尚未被访问过的其他各点到达现有MST最近的距离及其前驱结点信息。每当新添入一个新的顶点进入MST之后，则更新其余未处理顶点至最新状态下的最短路径长度与对应父节点位置[^2]。

import heapq

def prim_algorithm(graph, start_vertex):
    mst = []
    visited = set([start_vertex])
    edges = [(cost, start_vertex, to) for to, cost in graph[start_vertex].items()]
    heapq.heapify(edges)

    while edges:
        (cost, frm, to) = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((frm, to, cost))
            
            for next_to, next_cost in graph[to].items():
                if next_to not in visited:
                    heapq.heappush(edges, (next_cost, to, next_to))

    return mst

上述代码展示了如何利用优先队列优化后的版本来高效执行普里姆算法。这里`graph`是以邻接表形式表示的一张带权无向图，其中键代表各个顶点而值则是一个字典用来保存相邻顶点及其之间的代价。函数接收起始顶点作为参数并返回由三元组组成的列表——每项分别指示一条属于最终得到的MST内的边两端相连的两个端点加上它们之间关联的成本[^3]。