华为 8.31 机试第三题

#include <bits/stdc++.h>

using namespace std;

int maxDis = 1000;
int main()
{
    int D;
    int N;
    cin >> D >> N;
    vector<int> distance(N + 2);
    vector<int> weight(N + 2);
    distance[0] = 0;
    distance[N + 1] = D;
    weight[0] = 0;
    weight[N + 1] = 0;
    //标识在第i个加油站的时候花费的最小时间代价
    vector<int> dp(N + 2, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= N; i++)
    {
        cin >> distance[i];
        cin >> weight[i];
        if (distance[i] - distance[i - 1] > maxDis)
        {
            cout << -1 << endl;
            return 0;
        }
    }
    if (D <= maxDis)
    {
        cout << D / 100 << endl;
        return 0;
    }
    else
    {
        for (int i = 1; i <= N + 1; i++)
        {
            for (int j = i - 1; j >= 0; j--)
            {
                if (distance[i] - distance[j] > maxDis)
                    break;
                int add = 0;
                if (i != N + 1)
                    add = 1;
                dp[i] = min(dp[i], dp[j] + weight[i] + (distance[i] - distance[j]) / 100 + add);
            }
        }
    }
    cout << dp[N + 1] << endl;
    return 0;
}