luogu 1220 关路灯 区间dp

#include <bits/stdc++.h>  
#define ll long long  
#define N 1003   
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;     
void getmin(ll &a,ll b) 
{
    if(b<a) a=b;     
}   
ll x[N],sum[N],f[N][N][3],val[N];   
int main() 
{ 
    // setIO("input");        
    int n,pos,i,j,len;  
    scanf("%d%d",&n,&pos);   
    for(i=1;i<=n;++i) scanf("%lld%lld",&x[i],&val[i]);           
    for(i=1;i<=n;++i) sum[i]=sum[i-1]+val[i];   
    memset(f,0x3f,sizeof(f));       
    f[pos][pos][0]=f[pos][pos][1]=0;              
    for(len=2;len<=n;++len) 
    { 
        int l,r;   
        for(l=1;l+len-1<=n;++l) 
        {
            r=l+len-1;     
            getmin(f[l][r][0], f[l+1][r][0]+(x[l+1]-x[l])*(sum[n]-sum[r]+sum[l]));      
            getmin(f[l][r][0], f[l+1][r][1]+(x[r]-x[l])*(sum[n]-sum[r]+sum[l]));    
            getmin(f[l][r][1], f[l][r-1][1]+(x[r]-x[r-1])*(sum[n]-sum[r-1]+sum[l-1]));     
            getmin(f[l][r][1], f[l][r-1][0]+(x[r]-x[l])*(sum[n]-sum[r-1]+sum[l-1]));       
        }
    }
    printf("%lld\n",min(f[1][n][0], f[1][n][1]));     
    return 0; 
}