分析

将多游修理点按照位置递增排序。由于经过一个点便会立即修复它，所以每次被修复的点一定是一个连续的区间。由于修完一个区间后处于左右端点有后效性，要加进状态里。这样状态就出来了。

不难发现，最终答案能转化为 每个点立即修复的花费+增长的花费。我们只计算后者就好了。

设 \(f(i,j,p)\) 为修完区间 \([i,j]\)，处于 \(p\) 时增长的最小花费。\(p=0\) 时在 \(i\)，\(p=1\) 时在 \(j\)。

对于要修理的区间 \([i,j]\)，\([1,i-1] \cup [j+1,n]\) 都会增长 \(\frac{|x_j-x_j|}{v}\) 个 \(\Delta\)。所以我们将 \(\Delta\) 求出前缀和数组 \(g\)，这样就可以快速计算这个区间外增长的量。即 \[ F(x_i,x_j,i,j) = \frac{|x_i-x_j|}{v} \cdot g(n) - [g(j)-g(i-1)]\ \quad i \le j \] 特别地，当 \(i=j=0\) 时 \[ F(x_i,x_j,0,0) = \frac{|x_i-x_j|}{v} \cdot g(n) \] 转移显然有两种，对于区间 \([i,j]\)，一是转移到 \([i-1,j]\)，二是转移到 \([i,j+1]\)。再加上分别增长的量就好了。下面定义当 \(p=0\) 时，\(P=x_i\)，反之 \(P=x_j\)。 \[ f(i,j,p) = \min \begin{cases} f(i-1,j,0)+F(P,x_{i-1},i,j) \\ f(i,j+1,1)+F(P,x_{j+1},i,j) \end{cases} \] 开始先找到 \(X\) 左右的两个点，分别转移到这两个点上，取最小值就是答案了。

转移的时候注意判断边界。

最后看代码吧。

复杂度 \(O(n^2)\)。

CODE

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1006, inf=(1<<30);
int t, n;
double v, x, sum, ans, f[N][N][2], g[N];
bool vis[N][N][2];
struct O { double x, c, d; } s[N];
bool operator<(O a,O b) { return a.x<b.x; }
inline double F(double x1,double x2,int i,int j) {
    if(i>j) return 0;
    double dlt=0;
    if(i>0&&j>0) dlt+=g[j]-g[i-1];
    return (g[n]-dlt)*fabs(x2-x1)/v;
}
inline double dp(int i,int j,int p) {
    if(i==1&&j==n) return 0;
    double& w=f[i][j][p];
    if(vis[i][j][p]) return w;
    vis[i][j][p]=1, w=inf;
    double x=(p? s[j].x:s[i].x);
    if(i>1) w=min(w,dp(i-1,j,0)+F(x,s[i-1].x,i,j));
    if(j<n) w=min(w,dp(i,j+1,1)+F(x,s[j+1].x,i,j));
    return w;
}
inline void sol() {
    sum=0;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;++i) {
        scanf("%lf%lf%lf",&s[i].x,&s[i].c,&s[i].d);
        sum+=s[i].c;
    }
    sort(s+1,s+n+1);
    for(int i=1;i<=n;++i) g[i]=g[i-1]+s[i].d;
    s[0].x=-inf, s[n+1].x=ans=inf;
    for(int i=2;i<=n;++i) if(x>s[i-1].x&&x<s[i].x) {
        ans=min(ans,dp(i-1,i-1,0)+F(x,s[i-1].x,0,0));
        ans=min(ans,dp(i,i,0)+F(x,s[i].x,0,0));
        break;
    }
    printf("%d\n",(int)(ans+sum));
}
int main() { for(;scanf("%d%lf%lf",&n,&v,&x)&&n;sol()); }