这里很巧妙的注意一点是,你最后要把所有的豆子都吃掉,所以你只要看你多增加的尽量的少就好了
然后维护一段区间,表示的是吃掉这段区间里面的所有豆子的最小代价,然后发现最后一个是左端点或者右端点
你吃一段新的区间的同时会把不在这个区间的所有的豆子的另外代价都增加这里你可以维护一个前缀和就好了
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qmi(int a,int b,int mod){int res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;}
int n,q,m;
int st1;
// int e[N],ne[N],w[N],h[N],idx;
// void add(int a,int b,int c){
// e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
// }
struct Node{
int x,m,v;
bool operator<(const Node&W)const{
return x<W.x;
}
}node[N];
int dp[510][510][2];
int s[510];
//0-->left
int query(int l,int r){
return s[n]-s[r]+s[l-1];
}
int dfs(int l,int r,int st){
if(l>r)return inf;
if(l==r&&node[l].x==st1&&node[l].m==0)return dp[l][r][st] = 0;
if(~dp[l][r][st])return dp[l][r][st];
if(st){
dp[l][r][1] = min(dfs(l+1,r,1)+(node[l+1].x-node[l].x)*query(l+1,r)+node[l].m,
dfs(l+1,r,0)+(node[r].x-node[l].x)*query(l+1,r)+node[l].m);
//dp[l][r][1] = min(dfs(l+1,r,0)+(node[r].x-node[l].x)*query(l+1,r)+node[l].m,dp[l][r][st]);
}else{
dp[l][r][0] = min(dfs(l,r-1,1)+(node[r].x-node[l].x)*query(l,r-1)+node[r].m,
dfs(l,r-1,0)+(node[r].x-node[r-1].x)*query(l,r-1)+node[r].m);
//dp[l][r][0] = min(dfs(l,r-1,0)+(node[r].x-node[r-1].x)*query(l,r-1)+node[r].m,dp[l][r][st]);
}
return dp[l][r][st];
}
void solve()
{
cin>>n>>st1;
for(int i=1;i<=n;i++)cin>>node[i].x>>node[i].m>>node[i].v;
memset(dp,-1,sizeof dp);
n++;node[n].x = st1,node[n].m = node[n].v = 0;
sort(node+1,node+1+n);
//cout<<node[3].x<<"\n";
for(int i=1;i<=n;i++)s[i] = s[i-1]+node[i].v;
cout<<min(dfs(1,n,0),dfs(1,n,1));
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _;
//cin>>_;
_ = 1;
while(_--)solve();
return 0;
}