第一眼：哇，这题怎么这么眼熟！
见这道题：GO
传送门：GO
根本就是一样的题目嘛！
反正套路是一样的，就不说什么废话了，直接上代码吧。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int read(){ 4 int x=0,f=1; 5 char c=getchar(); 6 while(!isdigit(c)){ 7 if(c=='-') f=-1; 8 c=getchar(); 9 } 10 while(isdigit(c)){ 11 x=x*10+c-'0'; 12 c=getchar(); 13 } 14 return x*f; 15 } 16 const int N=60; 17 int n,c; 18 int f[N][N][2]; 19 int dis[N]; 20 int v[N],sum[N]; 21 int d(int i,int j){ 22 return dis[j]-dis[i]; 23 } 24 int val(int i,int j){ 25 return sum[n]-sum[j]+sum[i-1]; 26 } 27 int main(){ 28 n=read();c=read(); 29 for(int i=1;i<=n;i++){ 30 dis[i]=read(); 31 v[i]=read(); 32 sum[i]=sum[i-1]+v[i]; 33 } 34 memset(f,0x3f,sizeof(f)); 35 f[c][c][1]=f[c][c][0]=0; 36 for(int i=2;i<=n;i++){ 37 for(int j=1;j+i-1<=n;j++){//(i,j+i-1) 38 int k=j+i-1; 39 f[j][k][0]=min(f[j][k][0],min(f[j+1][k][0]+val(j+1,k)*d(j,j+1),f[j+1][k][1]+val(j+1,k)*d(j,k))); 40 f[j][k][1]=min(f[j][k][1],min(f[j][k-1][1]+val(j,k-1)*d(k-1,k),f[j][k-1][0]+val(j,k-1)*d(j,k))); 41 } 42 } 43 printf("%d",min(f[1][n][0],f[1][n][1])); 44 return 0; 45 }