NOIP2015 普及组 推销员 - 动态规划解法

这道题可以使用动态规划来解决。

首先，我们可以将住户按照到入口的距离从小到大排列。我们定义一个数组 dp，其中 dp[i] 表示当 X=i 时，阿明最多积累的疲劳值。我们需要求解 dp 的所有元素。

我们可以观察到，当 X=1 时，阿明只能向住户 N 推销产品，此时的疲劳值为 dp[1]=∑_(i=1)^N A_i。

当 X>1 时，我们需要考虑阿明向住户推销产品的次序。假设阿明在推销产品时，依次向住户 1, 2, …, i 推销，那么需要往返走路的疲劳值为 2 ⋅ S_i，推销的疲劳值为 ∑_(j=1)^i A_j。因此，如果阿明在推销产品时依次向住户 1, 2, …, i 推销，那么总的疲劳值为 dp[X-1] + 2 ⋅ S_i + ∑_(j=1)^i A_j。

我们可以遍历住户的顺序，求出所有阿明在推销产品时的总疲劳值。然后，我们可以更新 dp[X] 的值，即 dp[X]=max(dp[X-1] + 2 ⋅ S_i + ∑_(j=1)^i A_j)。最终，dp[N] 就是我们要求的答案。

具体实现时，我们可以使用两个数组 pre 和 cur 来存储 dp 的前一个状态和当前状态。在更新 dp[X] 的值时，可以使用滚动数组的技巧，只使用 pre 和 cur 两个数组进行更新。

下面是具体的代码实现：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> S(N);
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    vector<int> pre(N+1);  // 用于存储上一次循环的dp数组
    vector<int> cur(N+1);  // 用于存储当前循环的dp数组

    // 当X=1时，阿明只能向住户N推销产品
    int sumA = 0;
    for (int i = 0; i < N; i++) {
        sumA += A[i];
    }
    pre[1] = sumA;

    // 从X=2开始，更新dp数组
    for (int X = 2; X <= N; X++) {
        int maxFatigue = 0;
        int sumA = 0;
        for (int i = 0; i < N; i++) {
            sumA += A[i];
            maxFatigue = max(maxFatigue, pre[X-1] + 2 * S[i] + sumA);
        }
        pre.swap(cur);
        cur[X] = maxFatigue;
    }

    // 输出结果
    for (int X = 1; X <= N; X++) {
        cout << cur[X] << endl;
    }

    return 0;
}

该算法的时间复杂度是 O(N^2)，可以在给定的数据范围内求解。