单调队列求条

#include <iostream>
#include <deque>
#include <string.h>
#include <bits/stl_algo.h>
using namespace std;
struct shop{
    int x,f,c; //位置, 库存,价格
}s[501];
int k,n,e;
long long dp[501][10001];
inline bool cmp(shop a,shop b){
	return a.x<b.x;
}
int main() {
    ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> k >> e >> n;
	for(register int i=1; i<=n; i++)
		cin >> s[i].x >> s[i].f >> s[i].c;
	sort(s+1,s+n+1,cmp);
	memset(dp,0x3f,sizeof dp);
    dp[0][0] = 0;
    for(register int i = 1; i <= n; i++) {
        long long tcost;
        if(i == 1) tcost = s[i].x;
        else tcost = s[i].x-s[i-1].x;
        deque<pair<long long, int>> q; // 存储 {dp[i-1][j] + (j-x)^2 * tcost, j-x}
        for(register int j = 0; j <= k; j++) {
            while (q.size()&&q.front().second<j-min(k,s[i].f))
                q.pop_front(); // 弹出无效状态
            if(q.size())
                dp[i][j] = min(dp[i][j], q.front().first+j*s[i].c);
            long long price = dp[i-1][j]+j*j*tcost;
            // 保持队列单调递增
            while(q.size()&&q.back().first>=price)
                q.pop_back();
            q.push_back({price, j});
        }
    }
    // 加上从最后一个商店到家的运输成本
    cout << dp[n][k]+(e - s[n].x)*k*k << endl;
    return 0;
}