本文共 1597 字，大约阅读时间需要 5 分钟。

重新优化后的文章

E - 旅行商问题

有n个点，每个点有两个值a和c，从一个点i到另一个点j的花费是max(ci, aj - ai)。目标是找到一个遍历所有点且仅遍历一次的最小花费路径。

分析与思路

从一个点i到另一个点j的花费是max(ci, aj - ai)，这意味着在移动时，花费取决于当前点的c值或目标点的a值与起点a值的差值。为了最小化总花费，可以发现从a值较高的点向a值较低的点移动时，花费为ci，c值不可避免。因此，总花费包括所有c的和以及从最小a值到最大a值的a差值。

解决方案

将点按a值从小到大排序，按照1到n标号，问题转化为从1到n的最少额外花费。通过动态规划计算每个点的最小花费，选择最优路径。

动态规划公式

dp[i] = min{dp[j] - aj - cj}，其中i为当前点，j为前一个点。dp[n]即为从1到n的最小花费。

代码实现

代码首先读取输入，排序点，计算最小花费。通过遍历每个点，选择最优路径，最后输出最小花费。

代码解析

#include 
   
    
using namespace std;
typedef long long ll;
const ll N = 2e5 + 10;
bool vis[N];
struct node {
    ll a, c;
};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin >> n;
    for (ll i = 1; i <= n; ++i) {
        ll a, c;
        cin >> a >> c;
        if (i > 1 && a <= nodes[i-2].a) {
            // 确保a按升序排列
            // 这里可能需要调整排序逻辑
        }
        nodes[i] = {a, c};
    }
    sort(nodes + 1, nodes + n + 1, [](node x, node y) {
        return x.a < y.a;
    });
    ll pos = 1;
    ll ans = 0;
    ll h = nodes[pos].a + nodes[pos].c;
    for (ll i = 2; i <= n; ++i) {
        if (h < nodes[i].a + nodes[i].c) {
            ans += max(nodes[i].a - nodes[pos].a, nodes[pos].c);
            h = nodes[i].a + nodes[i].c;
            vis[pos] = 1;
            pos = i;
        }
    }
    ans += nodes[n].c;
    for (ll i = n - 1; i; --i) {
        if (!vis[i]) {
            ans += nodes[i].c;
        }
    }
    cout << ans << endl;
    return 0;
}
   

解释

输入处理：读取n和各点的a、c值。

排序：按a值从小到大排序，确保路径选择最优。

动态规划：从第一个点开始，计算每一步的最小花费，更新当前最优点。

计算最小花费：通过遍历所有点，累加最小花费，返回结果。

这个解决方案有效地将复杂的TSP问题转化为动态规划，确保在合理的时间复杂度内找到最优路径。