问题描述 一辆汽车将要从A城驶往B城。由于两城市之间的距离较远，即使这辆汽车在A城加满油，也无法在中途不加油的情况下抵达B城。幸运的是，两城之间的公路设有一些加油站，可以为汽车提供加油服务。 设两城之间的距离为 ，那么中间每 个单位距离就设有一座加油站（起点与终点没有）。汽车在加满油时，能行驶 个单位距离，为了保证汽车能顺利抵达B城，汽车必须在汽油耗尽前找到加油站进行加油。 由于每座加油站的汽油销售价格不同，这个汽车的驾驶员在出发前记录下了每个加油站的汽油销售价格，并给汽车加满了油。在第 个加油站需花费 的价格加满油（只能提供加满的服务）。为了尽量减少在旅途中的开销，驾驶员请聪明的你编程求出他最少要花费多少油钱。

输入格式 输入共两行。 第一行两个整数，输入用空格隔开的 和 。 第二行 个整数，第 个整数为 ，用空格隔开。

输出格式 共一行一个整数，即最少的花费。

样例输入1 5 2 2 4 8 6 Data 样例输出1 10 我的代码（40分）

#include <iostream>  
#include <vector>  
#include <deque>  
#define LONGLONG_MAX 0xFFFFFFFFFFFFFFFF
using namespace std;  

long long minCostToTravel(int N, int K, const vector<long long>& costs) {  
	if(K >= N) return 0;
    vector<long long> dp(N, LONGLONG_MAX);
	dp[0] = 0;
    deque<pair<int,long long > > q; 
    q.push_back(make_pair(0,0));
    for (int i = 1; i <= N; i++) {  
    
        while (!q.empty() && q.front().first < i - K) {  
            q.pop_front();  
        }  
  
        
        if (!q.empty()) {  
            dp[i] = dp[q.front().first] + q.front().second; 
			//cout << "   i : " << i << "		dp[q.front().first] : " << dp[q.front().first] << "  q.front().first : " << q.front().first <<"	dp[i] : " << dp[i]<< endl; 
        }  
  
        while (q.size() > 1 && costs[i - 1] <= q.back().second) {  
            q.pop_back();  
        }  
  
    
        q.push_back(make_pair(i, costs[i - 1]));  
    }  
  
    return dp[N];  
}  
  
int main() {  
	//freopen("zao.in","r",stdin);
	//freopen("concert.out","w",stdout);
    long long N,K;  
    cin >> N >> K; /* 单调队列 : O(n) , DP : O(n * k). */
    vector<long long> costs(N, 0);  
    for (int i = 1; i <= N - 1; i++) {  
        cin >> costs[i];
    }  
  
    long long minCost = minCostToTravel(N, K, costs);  
    cout << minCost << endl;  
  
    return 0;  
}