C++(g++ 7.5.0) 解法, 执行用时: 6ms, 内存消耗: 4376K, 提交时间: 2022-10-25 10:45:57

#include<bits/stdc++.h>
using namespace std;
class Node{
public:
	int x;
	int v;
	Node() : x(0) , v(0){}
	inline bool operator<(const Node& b) const {return this->x < b.x;}
};
class solution{
public:
	static const int N = 505;
	
	inline int houzhui(int qidian,int zhongdian,int l,int r){return (pos[zhongdian]-pos[qidian])*(sump[l]+sump[n]-sump[r]);}
	
	int operator()(int _n,int _c,vector<int> _pos,vector<int> _p){
		n=_n,c=_c;
		memset(dp,0x3f,sizeof(dp));
		sump[0]=0;
		for(int i = 1;i<=n;i++){
			pos[i] = _pos[i];
			sump[i]=sump[i-1] + _p[i];
		}
		
		dp[c][c][1]=dp[c][c][0]=0;
		
		for(int j=c;j<=n;j++){
			for(int i=j-1;i>0;i--){
				dp[i][j][0] = min(dp[i+1][j][0]+houzhui(i,i+1,i,j)  ,dp[i+1][j][1]+houzhui(i,j,i,j) );
				dp[i][j][1] = min(dp[i][j-1][0]+houzhui(i,j,i-1,j-1),dp[i][j-1][1]+houzhui(j-1,j,i-1,j-1)); 
			}
		}
		return min(dp[1][n][1],dp[1][n][0]);
	}
private:
	int n,c;
	int dp[N][N][2];
	int pos[N];
	int sump[N];
};

Node node[505];

int main(){
	int mi1=0,mi2=0;
	int coffee,flag;
	int n,start,m,summ=0,sumv=0;
	cin>>n>>start;
	vector<int> pos(n+1);
	vector<int> p(n+1);
	solution solve1,solve2;
	for(int i=1;i<=n;i++){
		cin>>node[i].x>>m>>node[i].v;
		summ+=m;
		sumv+=node[i].v;
	}
	sort(node,node+n+1);
	
	for(int i=1;i<=n;i++){
		pos[i] = node[i].x;
		p[i] = node[i].v;
	}
	
	/*先向左移动*/
	coffee = 0,flag = -1;
	for(int i=n;i>=1;i--){
		if(start > node[i].x ){
			flag = i;
			break;
		}
	}
	if(start == node[n].x) flag = n;
	
	if(flag != -1){
		coffee = (start - node[flag].x ) * (sumv);
		mi1 = coffee + solve1(n,flag,pos,p) + summ;
	}else{
		mi1 = 0x7fffffff;
	}
	
	/*先向右移动*/
	coffee = 0,flag = -1;
	for(int i=1;i<=n;i++){
		if(start < node[i].x){
			flag = i;
			break;
		}
	}
	if(start == node[1].x) flag = 1;
	
	if(flag != -1){
		coffee = (node[flag].x - start) * (sumv);
		mi2 = coffee + solve2(n,flag,pos,p) + summ;
	}else{
		mi2 = 0x7fffffff;
	}
	
	/*输出*/
	cout<<min(mi1,mi2);
	return 0;
}

C++(clang++11) 解法, 执行用时: 8ms, 内存消耗: 376K, 提交时间: 2020-11-29 09:58:03

#include<bits/stdc++.h>
using namespace std;
typedef struct a
{
	 int pos,m,v;
	 int dis;
};
int z,p;
a dots[505];
int vis[505];
int cmp(a x,a y)
{
	if(x.v==y.v)
	  return abs(x.pos-p)<abs(y.pos-p);
    return x.v>y.v;	  
}
int main()
{
  
   int nu;
   int tim=0;
   int ans;
   memset(vis,0,sizeof(vis));
   cin>>z>>p;
   nu=z;
   for(int i=0;i<nu;i++)
   	     cin>>dots[i].pos>>dots[i].m>>dots[i].v;
   while(nu>0)
   {
		sort(dots,dots+z,cmp);
		for(int i=0;i<z;i++)
			 if(!vis[i])
			 {
			 	vis[i]=1;
			 	tim+=abs(dots[i].pos-p);
			 	ans+=tim*dots[i].v+dots[i].m;
			 	p=dots[i].pos;
			 }
		nu--;
   }
   cout<<ans<<endl;
	return 0;
 }