本题极为经典，是动态规划中“未来费用”的计算， 因为起点固定且维修时间忽略，所以任意时间已经修复的点一定是一个连续的区间 。因此我们用d[i][j][k]表示已经修理完区间[i,j]

且现在正在点k ，如果k为0，在i点，如果k为1，在j点。这显然已经可以表示所有状态，那么怎么维护时间这个量呢？ 我们可以发现，每过t时间，没有维修的点都将增加费用，所以我们不妨先预处理求出每个区间的d值只和，然后将没有维修过的点乘以时间就好了，这样，我们就可以动态维护费用 。另外，最后的答案一定包括所有点的c值只和 。

另外需要注意虽然题目说答案不超过1000000000，但是中间值有可能超int ，所以我们不妨都用double 。

然而我用cout<

细节参见代码：

#include
  
   
using namespace std;
const double INF = 30000000000;
int n,kase = 0,vis[1005][1005][5];
double v,x,d[1005][1005][5],sum[1005];
struct point{
    double x,c,d;
    bool operator < (const point& v) const {
        return x < v.x;
    }
}a[1005];
double dp(int i,int j,int k) {
    if(i==1&&j==n) return 0;
    double& ans = d[i][j][k];
    if(vis[i][j][k] == kase) return ans;
    vis[i][j][k] = kase;
    ans = INF;
    double p = (k == 0 ? a[i].x : a[j].x);
    if(i>1) {
        double t = abs(a[i-1].x - p)/v;
        double u = (sum[i-1]+sum[n]-sum[j])*t+a[i-1].c;
        ans = min(ans,dp(i-1,j,0)+u);
    }
    if(j
   
    >n>>v>>x) { if(!n&&!v&&!x) return 0; for(int i=1;i<=n;i++) scanf(%lf%lf%lf,&a[i].x,&a[i].c,&a[i].d); sort(a+1,a+n+1); ++kase; sum[0] = 0; for(int i=1;i<=n;i++) { sum[i] = sum[i-1] + a[i].d; } a[0].x = -INF; a[n+1].x = INF; double ans = INF; for(int i=1;i<=n+1;i++) { if(a[i-1].x
    
     1) ans = min(ans,dp(i-1,i-1,0)+cur); t = abs(a[i].x - x)/v; cur = (sum[n])*t+a[i].c; if(i<=n) ans = min(ans,dp(i,i,1)+cur); } } printf(%.0lf ,floor(ans)); } return 0; }