芝士代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=51,INF=2147483640;
int n,c,pos[maxn],v[maxn];
int f[maxn][maxn],t[maxn][maxn];//f代表消耗功率，t代表到此的时间 
bool vis[maxn][maxn];			//0向左走(或者说指针在此区间左侧)，1向右走 
int red(){
	int as=0;int fl=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')fl=-1;ch=getchar();}
	while(isdigit(ch)){as=as*10+ch-'0';ch=getchar();}
	return as*fl;	
}

void init(){
	n=red();c=red();
	for(int i=1;i<=n;i++){
		pos[i]=red();
		v[i]=red();
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[i][j]=INF;
		}
	}
	f[c][c]=0;
}

void dp(){
	for(int k=2;k<=n;k++){
		for(int i=c-k+1,j=i+k-1;i<=c;i++,j++){
			if(i<=0||j>=n+1)		continue;			//跳过不适合的区间 
			if(j!=c+k-1){								//不在最右边（同下） 
				if(vis[i+1][j]==0){
					if(f[i+1][j]+(pos[i+1]-pos[i]+t[i+1][j])*v[i]<f[i][j]){
						f[i][j]=f[i+1][j]+(pos[i+1]-pos[i]+t[i+1][j])*v[i];
						t[i][j]=pos[i+1]-pos[i]+t[i+1][j];
						vis[i][j]=0;
					}
				}
				if(vis[i+1][j]==1){
					if(f[i+1][j]+(pos[j]-pos[i]+t[i+1][j])*v[i]<f[i][j]){
						f[i][j]=f[i+1][j]+(pos[j]-pos[i]+t[i+1][j])*v[i];
						t[i][j]=pos[j]-pos[i]+t[i+1][j];
						vis[i][j]=0;
					}
				}
			}	
			if(i!=c-k+1){								//不在最左边（但反错加个左边的数就溢出变负了）			
				if(vis[i][j-1]==0){
					if(f[i][j-1]+(pos[j]-pos[i]+t[i][j-1])*v[j]<f[i][j]){
						f[i][j]=f[i][j-1]+(pos[j]-pos[i]+t[i][j-1])*v[j];
						t[i][j]=pos[j]-pos[i]+t[i][j-1];
						vis[i][j]=1;
					}
				}
				if(vis[i][j-1]==1){
					if(f[i][j-1]+(pos[j]-pos[j-1]+t[i][j-1])*v[j]<f[i][j]){
						f[i][j]=f[i][j-1]+(pos[j]-pos[j-1]+t[i][j-1])*v[j];
						t[i][j]=pos[j]-pos[j-1]+t[i][j-1];
						vis[i][j]=1;
					}
				}
			}
//	调试	cout<<i<<" "<<j<<endl;
//	用的	cout<<f[i][j]<<" "<<t[i][j]<<" "<<vis[i][j]<<endl;
		}
	}
}

int main(){
	init();
	dp();
	printf("%d",f[1][n]);		//输出区间1-n的就行了 
	return 0;
}
//31980