区间dp（模板）

#include<bits/stdc++.h>
using namespace std;
int const N=57;
int n,c;
int a[N],w[N];
int f[N][N][2];
int main(){
	cin >> n >> c;
	for(int i=1;i<=n;++i){
		cin >> a[i] >> w[i];
		w[i]+=w[i-1];
	}
	memset(f,0x7f,sizeof f);
	f[c][c][0]=f[c][c][1]=0;
	for(int l=2;l<=n;++l){
		for(int i=1;i+l-1<=n;++i){
			int j=i+l-1;
			f[i][j][0]=min( f[i+1][j][0]+(a[i+1]-a[i])*(w[i]+w[n]-w[j]) ,
						    f[i+1][j][1]+(a[j]-a[i])*(w[i]+w[n]-w[j])  );
			f[i][j][1]=min( f[i][j-1][0]+(a[j]-a[i])*(w[i-1]+w[n]-w[j-1]),
							f[i][j-1][1]+(a[j]-a[j-1])*(w[i-1]+w[n]-w[j-1]) );
		}
	}
	int ans=min(f[1][n][0],f[1][n][1]);
	cout << ans;
	return 0;	
}