题目链接：https://www.luogu.com.cn/problem/P4544
解题思路：
首先我们可以将 \(N\) 家商店按照坐标 \(X_i\) 从小到大排序（可能会有一些商店坐标相同的情况，但是不影响）。
并且我们可以将家看做第 \(N+1\) 个商店（当然，\(F_{N+1} = 0\)）。
定义状态 \(F_{i,j}\) 表示在前 \(i\) 家商店买了恰好 \(j\) 吨饲料的总花费。
则状态转移方程为：
\[f_{i,j} = \min\limits_{0 \le k \le \min(j, F_i)} f_{i-1, j-k} + (X_i - X_{i-1}) \times (j-k)^2 + C_i \times k
\]
示例程序：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 505, maxk = 1e4 + 5;
long long f[maxn][maxk];
int K, E, n;
struct Node {int x, f, c;
} a[maxn];int main() {scanf("%d%d%d", &K, &E, &n);for (int i = 1; i <= n; i++)scanf("%d%d%d", &a[i].x, &a[i].f, &a[i].c);sort(a+1, a+n+1, [](Node a, Node b){return a.x < b.x;});a[n+1] = {E, 0, 0};memset(f, 0x3f, sizeof f);f[0][0] = 0;for (int i = 1, F = 0; i <= n+1; i++) {F = min(K, F + a[i].f);for (int j = 0; j <= F; j++) {for (int k = 0; k <= min(j, a[i].f); k++) {f[i][j] = min(f[i][j], f[i-1][j-k] + (long long)(a[i].x-a[i-1].x)*(j-k)*(j-k) + (long long)a[i].c * k);}}}printf("%lld\n", f[n+1][K]);return 0;
}
但是算法的时间复杂度为 \(O(N \times K^2)\)，会超时。（数据水了点， TLE 了一组，拿了 95 分）
接下来考虑如何优化。
考试将 \(j-k\) 替换为 \(k\)，上式变为：
\[f_{i,j} = \min\limits_{max(0, j-F_i) \le k \le j} f_{i-1,k} + (X_i - X_{i-1}) \cdot k^2 + C_i \cdot (j - k)
\]
其中，\(C_i \cdot j\) 是一个固定项（和 \(k\) 无关，可以提出来）
然后定义
\[g(i, k) = f_{i-1,k} + (X_i - X_{i-1}) \cdot k^2 - C_i \cdot k
\]
则
\(f_{i,j} = C_i \cdot j + \min\limits_{max(0, j-F_i) \le k \le j} g(i, k)\)
然后可以发现，随着 \(j\) 的增大，\(k\) 的左边界（\(max(0, j-F_i)\)）是逐渐变大的，\(k\) 右边界（\(j\)）也是逐渐变大的，所以我们可以用 单调队列 维护这个区间（任意时刻单调队列的队首对应的就是 \(\min\limits_{max(0, j-F_i) \le k \le j} g(i, k)\)）。
使用单调队列优化后，算法的时间复杂度就变为了 \(O(NK)\)（状态数 \(O(NK)\)，状态转移 \(O(1)\)）。
示例程序：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 505, maxk = 1e4 + 5;
long long f[maxn][maxk];
int K, E, n;
struct Node {int x, f, c;
} a[maxn];long long g(int i, int k) {return f[i-1][k] + (long long) (a[i].x - a[i-1].x) * k * k - (long long) a[i].c * k;
}int main() {scanf("%d%d%d", &K, &E, &n);for (int i = 1; i <= n; i++)scanf("%d%d%d", &a[i].x, &a[i].f, &a[i].c);sort(a+1, a+n+1, [](Node a, Node b){return a.x < b.x;});a[n+1] = {E, 0, 0};fill(f[0], f[0] + maxn*maxk, (long long)1e18);f[0][0] = 0;for (int i = 1, F = 0; i <= n+1; i++) {F = min(K, F + a[i].f);deque<int> que;for (int j = 0; j <= F; j++) {while (!que.empty() && que.front() < j - a[i].f)que.pop_front();while (!que.empty() && g(i, que.back()) >= g(i, j))que.pop_back();que.push_back(j);f[i][j] = (long long) a[i].c * j + g(i, que.front());}}printf("%lld\n", f[n+1][K]);return 0;
}
