toj_2938.cpp

来自「Tianjin University Online Judge 的80多道题目 」· C++ 代码 · 共 67 行

#include<cstdio>
#include<cmath>
#define MAXHOUSE 210
int h , c;
double x[ MAXHOUSE ] ,  dp[ MAXHOUSE ][ MAXHOUSE ] , cost[ MAXHOUSE ][ MAXHOUSE ];

void findCost()
{
    int i , j , xjMxi  , jMi , k;
    double diff[ MAXHOUSE ][ MAXHOUSE ];
    for( i = 1; i <= h; i++ ){
        for( j = i + 1 ; j <= h; j++ )
            diff[ i ][ j ] = x[ j ]  - x[ i ];
    }
            
    for( i = 1; i <= h - 1; i++ ){
        for( j = i; j <= h; j ++ ){
            cost[ i ][ j ] = 0;
            jMi = j - i;
            for( k = i + 1 ; k < j;k++ )
                cost[ i ][ j ] += fabs( -diff[ i ][ k ] + diff[ i ][ j ] * ( k - i ) / jMi );
        }
    }
}

void dinamicProgram()
{
    int i , j , k;
    double min , currentValue;
    for( i = 1; i <= c; i++ )
        dp [ i ] [ i ] = 0;
    for( i = 2; i <= h; i++ ){
        for( j = 2; j <= c; j++ ){
            min = 1e30;
            for( k = 1; k < i - j; k++ ){
                currentValue = dp[ i - k ][ j - 1 ] + cost[ i - k ][ i ];
                if( min > currentValue )
                    currentValue = min;
            }
            
        }
    }
}

            
        
int main()
{
    int i , j , k , testCase;
    scanf( "%d" , &testCase );
    while ( testCase-- ){
        scanf( "%d%d" , &h , &c );
        for( i = 1; i <= h; i++ ){
            scanf ( "%lf" , &x[ i ] );
        }
        findCost();
        dinamicProgram();
        printf( "%lf\n" , dp[ h ][ c ] );
    }
    return 0;
}