单调队列求条
#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;
}