rt 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 55;
int n,c;
int m[maxn],w[maxn],s[maxn],q[maxn];
int f[maxn][maxn][2];
int main(){
	cin>>n>>c;
	for(int i = 1;i<=n;i++){
		cin>>m[i]>>w[i];
		s[i] = s[i-1]+w[i];
		q[i] = q[i-1]+w[i]*m[i];
	}
	memset(f,0x3f3f,sizeof(f));
	f[c][c][0]=f[c][c][1]=0;
	for(int len = 2;len<=n;len++){
		for(int i = 1,j = i+len-1;j<=n;i++,j++){
			f[i][j][0] = min(f[i+1][j][0]+w[i+1]*(m[i+1]-m[i])+(s[n]-s[j]+s[i-1])*(m[i+1]-m[i]),f[i+1][j][1]+m[j]*(s[j-1]-s[i-1])-(q[j-1]-q[i-1])+(s[n]-s[j]+s[i-1])*(m[j]-m[i]));
			f[i][j][1] = min(f[i][j-1][1]+w[j-1]*(m[j]-m[j-1])+(s[n]-s[j]+s[i-1])*(m[j]-m[j-1]),f[i][j-1][0]+(q[j]-q[i])-m[i]*(s[j]-s[i-1])+(s[n]-s[j]+s[i-1])*(m[j]-m[j-1]));
		}
	}
	cout<<min(f[1][n][0],f[1][n][1]);
}