rt

可以过udebug上的大样例

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
struct node{
	double pos,fix,delta;
}dat[1065];
bool cmp(node a,node b){
	return a.pos<b.pos;
}
double dp[1065][1065][2],sumdelta[1065],v;//dp[i][j][k]修复完[i,j]，且在i/j点的最小费用和必定会花费的费用，sumdelta[i]->dat[1].delta+dat[2].delta+...+dat[i].delta
int64 n,x;//假设GWARR从i向左走修理i-1，GWARR走的时间为((dat[i].pos-dat[i-1].pos)/v)，此时所有没有被修理的长城必然会产生的费用为[1~i-1]与[j+1~n]的两端区间的delta之和乘时间
//最终的答案就是所有长城在时刻0时所花费的费用val+min(dp[1][n][0],dp[1][n][1])
signed main(){
	while(true){
		cin>>n>>v>>x;
		if(!n) return 0;
		for(int i=1;i<=n;i++) cin>>dat[i].pos>>dat[i].fix>>dat[i].delta;
		dat[++n]=node{x*1.0,0.0,0.0};//加入起点
		sort(dat+1,dat+n+1,cmp);//将他有序化
		int start,val=0;//起点位置
		for(int i=1;i<=n;i++){
			val+=dat[i].fix;
			if(dat[i].pos==1.0*x&&dat[i].fix==0.0&&dat[i].delta==0.0) start=i;
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++) dp[i][j][0]=dp[i][j][1]=1e12;
		memset(sumdelta,0,sizeof(sumdelta));
		dp[start][start][0]=dp[start][start][1]=0.0;//起点不需要任何话费
		for(int i=1;i<=n;i++) sumdelta[i]=sumdelta[i-1]+dat[i].delta;
		for(int l=1;l<=n;l++)
			for(int i=1;i+l-1<=n;i++){
				int j=i+l-1;
				if(i-1>1) dp[i-1][j][0]=min(dp[i-1][j][0],min(dp[i][j][0]+(dat[i].pos-dat[i-1].pos)/v*(sumdelta[i-1]+sumdelta[n]-sumdelta[j]),dp[i][j][1]+(dat[j].pos-dat[i-1].pos)/v*(sumdelta[i-1]+sumdelta[n]-sumdelta[j])));//GWARR可以从i走到i-1，也可以从j走到i-1
				if(j+1<=n) dp[i][j+1][1]=min(dp[i][j+1][1],min(dp[i][j][1]+(dat[j+1].pos-dat[j].pos)/v*(sumdelta[i-1]+sumdelta[n]-sumdelta[j]),dp[i][j][0]+(dat[j+1].pos-dat[i].pos)/v*(sumdelta[i-1]+sumdelta[n]-sumdelta[j])));
			}
		cout<<int64(1.0*val+min(dp[1][n][0],dp[1][n][1]))<<endl;
	}
}