#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1005;
double f[N][N][2], v, sx, c[N], d[N], s[N], x[N], res;
int n;
struct node
{
    double x, c, d;
} e[N];
bool cmp(node a, node b)
{
    return a.x < b.x;
}
double m_min(double a, double b)
{
    return a < b ? a : b;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    while (cin >> n, n)
    {
        cin >> v >> sx, res = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                f[i][j][0] = f[i][j][1] = 1e10;
        for (int i = 1; i <= n; i++)
        {
            double x, c, d;
            cin >> x >> c >> d, e[i] = {x, c, d};
        }
        sort(e + 1, e + 1 + n, cmp);
        for (int i = 1; i <= n; i++)
            x[i] = e[i].x, c[i] = e[i].c, d[i] = e[i].d, s[i] = s[i - 1] + d[i], res += c[i];
        for (int i = 1; i <= n; i++)
            f[i][i][0] = f[i][i][1] = s[n] * (abs(sx - x[i]) / v);
        for (int len = 2; len <= n; len++)
            for (int l = 1, r = l + len - 1; r <= n; l++, r++)
            {
                f[l][r][0] = min(min(f[l][r][0], f[l + 1][r][0] + (s[l] + s[n] - s[r]) * (x[l + 1] - x[l]) / v),
                                 min(f[l][r][0], f[l + 1][r][1] + (s[l] + s[n] - s[r]) * (x[r] - x[l]) / v));
                f[l][r][1] = min(min(f[l][r][1], f[l][r - 1][1] + (s[l - 1] + s[n] - s[r - 1]) * (x[r] - x[r - 1]) / v),
                                 min(f[l][r][1], f[l][r - 1][0] + (s[l - 1] + s[n] - s[r - 1]) * (x[r] - x[l]) / v));
            }
        cout << (int)(res + min(f[1][n][0], f[1][n][1])) << "\n";
    }
}

这题Udebug上的样例比较弱，但是我也能过，重复多测大样例，比题解满了快一倍吧，但我看了一下代码，大O复杂度没问题啊？