正题
第四题：关路灯
这题主要就是用区间Dp（莫队可做？）。
那么一个以关灯区间的状态有两种，记录左端点和记录右端点。
我们用f[i][j][0]来表示当前是在左端点。
用f[i][j][1]来表示当前是在右端点。
一个点在左端点时，到他的状态有：f[i+1][j][1],f[i+1][j][0]（从上个区间的右端点和左端点过来）;
一个点在右端点时，到他的状态有：f[i][j-1][1]，f[i][j-1][0]（从上个区间的右端点和左端点过来）;
那么当在走过来的同时，会浪费一定的电，如果当前要 求左端点，从上个区间左端点过来那么就浪费了距离乘瓦数。其他的同理，做一个前缀和a[i]来统计一下0到i的距离即可。
#include<cstdio>
#include<cstdlib>
#include<cstring>
int n,k;
struct node{int x,y;};
node s[55];
long long f[55][55][2];
int qian[55];
long long min(long long x,long long y)
{
return x<y?x:y;
}
int main()
{
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d %d",&s[i].x,&s[i].y);
qian[1]=s[1].y;
for(int i=2;i<=n;i++)
qian[i]=qian[i-1]+s[i].y;
memset(f,63,sizeof(f));
f[k][k][1]=0;
f[k][k][0]=0;
for(int l=1;l<=n-1;l++)
for(int i=1;i+l<=n;i++)
{
int j=i+l;
long long a=f[i+1][j][0]+(s[i+1].x-s[i].x)*(qian[n]-qian[j]+qian[i]);
long long b=f[i+1][j][1]+(s[j].x-s[i].x)*(qian[n]-qian[j]+qian[i]);
f[i][j][0]=min(a,min(f[i][j][0],b));;
a=f[i][j-1][0]+(s[j].x-s[i].x)*(qian[n]-qian[j-1]+qian[i-1]);
b=f[i][j-1][1]+(s[j].x-s[j-1].x)*(qian[n]-qian[j-1]+qian[i-1]);
f[i][j][1]=min(a,min(f[i][j][1],b));
}
printf("%d",min(f[1][n][0],f[1][n][1]));
}