hdu 1227単純dp+中位数の性質

列数X 1,X 2,X 3,...,Xn
f(x)=|X1-x|+|X2-x|+|X3-x|+...+|Xn-x|
x＝数列中位数ではf(x)が最小となる
この問題を作る前に必ずこの結論を知ってから、どのように問題を解くかを考え始めます.まず、状態を定義します.
dp[i][j]、i世代はすでにいくつかの供給ステーションが建設されていることを示し、jは現在いくつかの都市に供給されていることを表している.
では、現在の状況を更新するには、前の供給ステーションの組立状態を見つけなければならないので、最後の都市を列挙して、iからjの間で、それから中位数の性質のため、私たちが供給ステーションを建設するたびに必ず中位数の位置にある.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#define MAX 207

using namespace std;

int n,m;
int dp[MAX][MAX];
int d[MAX];
int c[MAX][MAX];

int main ( )
{
    int cc = 1;
    while ( ~scanf ( "%d%d" , &n , &m  ) , n+m )
    {
        for ( int i = 1 ; i <= n ; i++ ) scanf ( "%d" , &d[i] );
        memset ( c, 0 , sizeof ( c ) );
        for ( int i = 1 ; i <= n ; i++ )
            for ( int j = i; j <= n ; j++ )
                for ( int k = i ; k <= j ; k++ )
                    c[i][j] += abs ( d[k] - d[(i+j)/2] );
        memset ( dp , 0x7f , sizeof ( dp ) );
       // cout << dp[0][0] << endl;
        dp[0][0] = 0;
        for ( int i = 1 ; i <= n ; i++ )
            dp[1][i] = c[1][i];
        for ( int i = 2 ; i <= m ; i++ )
            for ( int j = i ; j <=  n ; j++ )
                for ( int k = i-1 ; k < j ; k++ )
                    dp[i][j] = min ( dp[i][j] , dp[i-1][k] + c[k+1][j] );
        printf ( "Chain %d
" , cc++ );
        printf ( "Total distance sum = %d
" , dp[m][n] );
        puts ( "" );
    }
}