RT 一开始我为了验证自己的方程是否对的 搞了个33pts的暴力 所以式子应该没问题？ 后来我就优化了下就66pts 然后发现似乎可以到O(n) 然后就推了个式子 然后一直WA 只有11pts 若能告知错误 感激不尽

30pts

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>

#define N (int)(1e6+5)
#define int long long
#define inf (int)(2e18)

using namespace std; 

int n,f[N][2],x[N],p[N],c[N];

int rd() {
	int f=1,sum=0; char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return sum*f;
}

void pr(int x) {
	if(x<0) {putchar('-');x=-x;}
	if(x>9) pr(x/10);
	putchar(x%10+'0');
}

int solve(int l,int r) {
	int qwq=0;
	for(int i=l+1;i<=r-1;i++) qwq+=p[i]*(x[r]-x[i]);
	return qwq; 
}

signed main() {
	n=rd();
	for(int i=1;i<=n;i++) x[i]=rd(),p[i]=rd(),c[i]=rd();
	f[n][1]=c[n]; f[n][0]=inf;
	for(int i=n-1;i>=1;i--) {
		int qwq=inf;
		for(int j=i+1;j<=n;j++) qwq=min(qwq,f[j][1]+(x[j]-x[i])*p[i]+solve(i,j));
		f[i][0]=qwq;
		qwq=inf;
		for(int j=i+1;j<=n;j++) qwq=min(qwq,f[j][1]+solve(i,j));
		f[i][1]=qwq+c[i];	
	}	
	pr(min(f[1][0],f[1][1]));
	return 0;
}

66pts

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>

#define N (int)(1e6+5)
#define int long long
#define inf (int)(2e18)
#define min(A,B) (A>B?B:A)

using namespace std; 

int n,f[N][2],x[N],p[N],c[N],s[N],sp[N];

int rd() {
	int f=1,sum=0; char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return sum*f;
}

void pr(int x) {
	if(x<0) {putchar('-');x=-x;}
	if(x>9) pr(x/10);
	putchar(x%10+'0');
}

signed main() {
	n=rd();
	for(int i=1;i<=n;i++) x[i]=rd(),p[i]=rd(),c[i]=rd();
	for(int i=1;i<=n;i++) s[i]=s[i-1]+p[i]*x[i],sp[i]=sp[i-1]+p[i];
	f[n][1]=c[n]; f[n][0]=inf;
	for(int i=n-1;i>=1;i--) {
		int qwq=inf;
		for(int j=i+1;j<=n;j++) qwq=min(qwq,f[j][1]+(sp[j-1]-sp[i-1])*x[j]-(s[j-1]-s[i-1]));
		f[i][0]=qwq;
		qwq=inf;
		for(int j=i+1;j<=n;j++) qwq=min(qwq,f[j][1]+(sp[j-1]-sp[i])*x[j]-(s[j-1]-s[i]));
		f[i][1]=qwq+c[i];	
	}	
	pr(min(f[1][0],f[1][1]));
	return 0;
}

WA 11pts的代码

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>

#define N (int)(1e6+5)
#define int long long
#define inf (int)(2e18)
#define min(A,B) (A>B?B:A)
#define db double

using namespace std; 

int n,f[N][2],x[N],p[N],c[N],s[N],sp[N],q1[N],h1=1,t1=1,q2[N],h2=1,t2=1;

int rd() {
	int f=1,sum=0; char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return sum*f;
}

void pr(int x) {
	if(x<0) {putchar('-');x=-x;}
	if(x>9) pr(x/10);
	putchar(x%10+'0');
}

db solve(int j,int k) {
	return (db)(f[j][1]+sp[j-1]*x[j]-s[j-1]-f[k][1]-sp[k-1]*x[k]+s[k-1])/(db)(x[j]-x[k]);
}

signed main() {
	n=rd();
	for(int i=1;i<=n;i++) x[i]=rd(),p[i]=rd(),c[i]=rd();
	for(int i=1;i<=n;i++) s[i]=s[i-1]+p[i]*x[i],sp[i]=sp[i-1]+p[i];
	f[n][1]=c[n]; f[n][0]=inf;
	q1[++t1]=n; q2[++t2]=n;
	for(int i=n-1;i>=1;i--) {
		while(h1<t1&&solve(q1[h1],q1[h1+1])>sp[i-1]) ++h1;
		while(h2<t2&&solve(q2[h2],q2[h2+1])>sp[i]) ++h2;
		int j=q1[h1];
		f[i][0]=f[j][1]+(sp[j-1]-sp[i-1])*x[j]-(s[j-1]-s[i-1]);
		j=q2[h2];
		f[i][1]=f[j][1]+(sp[j-1]-sp[i])*x[j]-(s[j-1]-s[i])+c[i];
		while(h1<t1&&solve(q1[t1],q1[t1-1])<=solve(q1[t1],i)) --t1;
		q1[++t1]=i;
		while(h2<t2&&solve(q2[t2],q2[t2-1])<=solve(q2[t2],i)) --t2;
		q2[++t2]=i;
	}	
	pr(min(f[1][0],f[1][1]));
	return 0;
}