ACM-ICPC算法竞赛：DAG上的动态规划详解与C++实现

ACM-ICPC算法竞赛：DAG上的动态规划详解与C++实现

引用

CSDN

1.

https://blog.csdn.net/tang7mj/article/details/138243848

DAG上的动态规划概念

在有向无环图（DAG）中，每个顶点代表一个状态，每条有向边代表从一个状态到另一个状态的转移，边的权值可以理解为状态转移的成本。DAG上的动态规划的关键在于找到一个状态转移方程，它可以优雅地解决问题，如找到从起点到终点的最短路径、最长路径或计数路径的数量等。

工作原理

DAG上的DP工作原理很简单：从图的一个排序（如拓扑排序）开始，确保当我们处理一个顶点时，从这个顶点出发能到达的顶点尚未处理。这样，我们就可以利用已经计算过的结果来解决当前顶点的问题。DAG上的DP算法通常涉及以下步骤：

1. 拓扑排序: 首先进行拓扑排序，确保所有的边都从排序中的前面指向后面。
2. 初始化: 根据问题的不同，对起始点进行初始化。
3. 状态转移: 遍历拓扑排序的结果，根据状态转移方程来更新每个顶点的值。
4. 解答构造: 根据DP表中的值，构造最终答案。

C++实现示例

以下是在DAG上进行DP的简化C++实现。为了专注于DP逻辑，我们假设图的结构和边的权重已经给出。

#include <vector>
#include <algorithm>
// 假设Graph已经给出，graph[i]存储了从顶点i出发的边的列表，每条边表示为(pair<int,int>)，包含目标顶点和权重。
using Edge = pair<int, int>;
vector<vector<Edge>> graph;
// dp数组，用于存储到每个顶点的最优值。
vector<int> dp;
// visited数组，用于记录顶点是否被访问过。
vector<bool> visited;
// 存储拓扑排序的结果。
vector<int> topoSort;
// 对图进行拓扑排序的函数。
void topologicalSort(int v) {
    visited[v] = true;
    for (Edge& edge : graph[v]) {
        if (!visited[edge.first])
            topologicalSort(edge.first);
    }
    topoSort.push_back(v);
}
// 进行动态规划的函数。
void dagDynamicProgramming() {
    // 假设起始顶点是0，目标是计算到其他所有顶点的最长路径。
    dp[0] = 0; // 初始状态的值
    // 遍历拓扑排序的结果，进行状态转移。
    for (int i = 0; i < topoSort.size(); ++i) {
        int v = topoSort[i];
        for (Edge& edge : graph[v]) {
            int u = edge.first;
            int weight = edge.second;
            // 状态转移方程：dp[u] = max(dp[u], dp[v] + weight);
            dp[u] = max(dp[u], dp[v] + weight);
        }
    }
}
int main() {
    // 假设graph的结构和边权已经定义好。
    int n = graph.size();
    dp.assign(n, INT_MIN); // 如果是最长路径问题，初始化为负无穷。
    visited.assign(n, false);
    
    // 执行拓扑排序。
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            topologicalSort(i);
    }
    reverse(topoSort.begin(), topoSort.end()); // 反转以得到正确的顺序。
    // 执行动态规划。
    dagDynamicProgramming();
    // 输出到所有顶点的最长路径。
    for (int i = 0; i < n; ++i) {
        cout << "最长路径到达顶点 " << i << " : " << dp[i] << endl;
    }
    return 0;
}

这段代码提供了DAG上DP算法的一个框架，你可以根据实际问题调整状态转移方程和初始化方式。在实际竞赛中，具体的问题需要对此框架做出相应的调整以适应不同的问题设定。