P1220 关路灯

已被关的区间是封闭连续的，加之还要知道人是在左端点还是在右端点，

所以设f[i][j][0/1]表示现在[i,j]被关闭的最小花费，且0人在左端点，1人在右端点

初始f[st][st][0/1]=0，其他=oo

转移的费用通过两点路程差*左右两段未被关的区间的功率之和

功率和可通过前缀和计算

ans=min(f[1][n][0],f[1][n][1])

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}
const int N=55;
int n,st,p[N],s[N],f[N][N][2];
inline int que(int l,int r){
    return s[r]-s[l-1];
}
signed main(){
    read(n);read(st);
    for(int i=1;i<=n;i++){
        read(p[i]);
        read(s[i]);
        s[i]+=s[i-1];
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) if(i!=st||j!=st)
            f[i][j][0]=f[i][j][1]=0x3f3f3f3f;
    for(int j=st;j<=n;j++)
        for(int i=j-1;i>=1;i--){
            f[i][j][0]=min(f[i+1][j][0]+(p[i+1]-p[i])*(que(1,i)+que(j+1,n)),f[i+1][j][1]+(p[j]-p[i])*(que(1,i)+que(j+1,n)));
            f[i][j][1]=min(f[i][j-1][0]+(p[j]-p[i])*(que(1,i-1)+que(j,n)),f[i][j-1][1]+(p[j]-p[j-1])*(que(1,i-1)+que(j,n)));
        }
    write(min(f[1][n][0],f[1][n][1]));
}