练86.1 旅行

解题思路

将固定旅馆和新增旅馆合并排序。dp[i]表示到达旅馆i的路线数，dp[起点]=1；若两旅馆距离在[A,B]，就把前者dp加到后者。最后7000位置的dp是总方案数。

正确性说明

每条到i的路线有唯一倒数第二个旅馆j，合法j满足每日距离条件。这些按j分类的路线互不重复且覆盖全部，求和得到dp[i]。

易错点

起点0与终点7000也在表内；每日距离包含两个端点。

复杂度

H家旅馆，时间O(H²)，空间O(H)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int A, B, N;
    cin >> A >> B >> N;
    vector<int> p = {0,    990,  1010, 1970, 2030, 2940, 3060,
                     3930, 4060, 4970, 5030, 5990, 6010, 7000};
    while (N--) {
        int x;
        cin >> x;
        p.push_back(x);
    }
    sort(p.begin(), p.end());
    vector<unsigned long long> dp(p.size());
    dp[0] = 1;
    for (size_t i = 1; i < p.size(); i++)
        for (size_t j = 0; j < i; j++)
            if (p[i] - p[j] >= A && p[i] - p[j] <= B)
                dp[i] += dp[j];
    cout << dp.back() << "\n";
    return 0;
}