P1220 关路灯

#include <iostream>
using namespace std ;
int weast ( int , int , int , int );
const int N = 55 ;
int n , c ;
int f [ N ] [ N ] [ 3 ] ;
//0代表在i处，1代表在j处
int sum [ N ] , location [ N ] ;
int main ( ) {
    // freopen ( "text.in" , "r" , stdin ) ;
    cin >> n >> c ;
    for ( int i = 1 ; i <= n ; i ++ ) {
        cin >> location [ i ] >> sum [ i ] ;
        sum [ i ] += sum [ i - 1 ] ;
    }
    for ( int i = 1 ; i <= n ; i ++ ) {
        for ( int j = 1 ;  j <= n ; j ++ ) {
            f [ i ] [ j ] [ 0 ] = f [ i ] [ j ] [ 1 ] = ( 1 << 30 ) ;
        }
    }
    f [ c ] [ c ] [ 0 ] = f [ c ] [ c ] [ 1 ] = 0;
    for ( int r = c ; r <= n ; r ++ ) {
            for ( int l = r - 1 ; l >= 1 ; l -- ) {
            if ( l == r && r == c ) continue;
            f [ l ] [ r ] [ 0 ] =
                min ( f [ l + 1 ] [ r ] [ 0 ] + weast ( l + 1 , l , l + 1 , r ) , f [ l + 1 ] [ r ] [ 1 ] + weast ( r , l , l + 1 , r ) ) ;
            f [ l ] [ r ] [ 1 ] =
                min ( f [ l ] [ r - 1 ] [ 0 ] + weast ( r , l , l , r - 1 ) , f [ l ] [ r - 1 ] [ 1 ] + weast ( r , r - 1 , l , r - 1 ) ) ;
        }
    }
    // cout << f [ c ] [ c + 1 ] [ 0 ]  << " " << f [ c ] [ c + 1 ] [ 1 ] << endl;
    cout << min ( f [ 1 ] [ n ] [ 0 ] , f [ 1 ] [ n ] [ 1 ] ) ;
     return 0 ;
}
int weast ( int x , int y , int l , int r ) {
    return ( location [ x ] - location [ y ] )*( sum [ n ] - sum [ r ] + sum [ l - 1 ] ) ;
}