动态规划在图论中的应用：宝石收集问题解析

1. 题目背景与核心需求解析

这道来自BalticOI 2003的Gem气垫车题目，本质上是一个典型的动态规划在图论中的应用。题目描述了一辆气垫车需要在由节点和边组成的网络中进行移动，每个节点有特定的宝石价值，气垫车需要选择最优路径来最大化收集的宝石总价值。

1.1 题目建模要点

我们需要将这个问题转化为图论模型：

• 节点代表地点，附带宝石价值
• 边代表气垫车可移动的路径
• 移动规则决定了状态转移的方式

关键约束在于气垫车的特殊移动方式：每次移动会消耗与当前节点宝石价值相关的能量，且不能连续经过两个相同价值的节点。这直接影响了我们的状态设计。

1.2 动态规划状态设计

经过分析，我们需要设计一个二维DP状态：

• dp[u][c] 表示到达节点u时，上一个节点颜色为c时的最大宝石价值
• c的取值范围需要根据题目给出的宝石价值范围确定

状态转移方程需要考虑：

1. 当前节点颜色不能与前驱节点相同
2. 转移时的价值累加规则
3. 边界条件的处理（起始节点的初始化）

2. 算法实现细节

2.1 数据结构选择

对于图的存储，考虑到信奥题的数据规模（通常n≤1e5），我们采用邻接表表示法：

cpp复制vector<vector<int>> adj(n+1);  // 节点从1开始编号
vector<int> value(n+1);        // 各节点宝石价值

2.2 动态规划实现框架

采用记忆化搜索的方式实现DP，避免复杂的迭代顺序处理：

cpp复制int dp[MAX_N][MAX_C];  // 根据题目约束确定MAX_C值

int dfs(int u, int last_color, int parent) {
    if(dp[u][last_color] != -1) 
        return dp[u][last_color];
    
    int res = 0;
    for(int v : adj[u]) {
        if(v == parent) continue;
        // 状态转移逻辑
        for(int c = 1; c <= MAX_C; ++c) {
            if(c == l