很容易想到f[i]为前i项的最优价值，但是我一直在纠结如果重量满了该怎么办。
正解有点枚举的味道。
就是枚举当前这辆车与这辆车以前的组合一组，在能组的里面取最优的。
然后要记得初始化，因为有min，所以除0外初始化为最大，f[0] = 0
这实际上可以抽象出一种模型，就是一个区间线性分组的模型，都可以用这道题的方法写。
#include#include #include #define REP(i, a, b) for(int i = (a); i < (b); i++)using namespace std;typedef long long ll;const int MAXN = 1123;double v[MAXN], f[MAXN];int w, len, n;ll a[MAXN];int main(){ scanf("%d%d%d", &w, &len, &n); REP(i, 1, n + 1) { int x, y; scanf("%d%d", &x, &y); a[i] = a[i - 1] + x; v[i] = len / (double)y * 60.0; } f[0] = 0.0; REP(i, 1, n + 1) { f[i] = 999999999999999.0; //一定要开很大，否则WA double t = 0; for(int j = i; j >= 1; j--) { if(a[i] - a[j - 1] > w) break; t = fmax(t, v[j]); f[i] = fmin(f[i], f[j - 1] + t); } } printf("%.1lf\n", f[n]); return 0; }