#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn = 79;
const ll inf = 1LL << 60;

int N, C, H[maxn];
ll dp[maxn][maxn][maxn];

template<class T>
inline void Min(T &x, T t) {
if(t < x) x = t;
}

struct Node {
int d, v, p;
bool operator < (const Node &o) const {
return d < o.d;
}
} o[maxn];

ll Dp(int l, int r, int v) {
if(l > r) return 0;
ll &t = dp[l][r][v];
if(~t) return t;
int d = o[r].p - o[l - 1].p;
if(l == r)
return t = d + (o[l].v >= v ? 0 : C);
t = inf;
for(int i = l; i <= r; i++) {
Min(t, Dp(l, i - 1, v) + Dp(i + 1, r, v) + C + d);
if(o[i].v >= v)
Min(t, Dp(l, i - 1, o[i].v) + Dp(i + 1, r, o[i].v) + d);
}
return t;
}

int main() {

scanf("%d%d", &N, &C);
for(int i = 1; i <= N; i++) scanf("%d", &o[i].d);
for(int i = 1; i <= N; i++) scanf("%d", &o[i].v);
for(int i = 1; i <= N; i++) scanf("%d", &o[i].p);

sort(o + 1, o + N + 1);
o[0].p = 0;
for(int i = 1; i <= N; i++) {
o[i].p += o[i - 1].p;
H[i - 1] = o[i].v;
}
sort(H, H + N);
int hn = unique(H, H + N) - H;
for(int i = 1; i <= N; i++)
o[i].v = lower_bound(H, H + hn, o[i].v) - H;
memset(dp, -1, sizeof dp);
ll ans = inf;
for(int i = 0; i < hn; i++)
Min(ans, Dp(1, N, i));
cout << ans << "\n";

return 0;
}

dp http://www.cnblogs.com/JSZX11556/p/5188328.html

不会

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std ;

#define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )

typedef long long ll ;

const int maxn = 75 ;

struct ntype {
int d , v , u ;
bool operator < ( const ntype &x ) const {
return d < x.d ;
}
} t[ maxn ] ;

int a[ maxn ] , b[ maxn ] , n , m = 0 , k , w[ maxn ] , sum[ maxn ] ;

inline int getp( int x ) {
if ( x == b[ 1 ] ) return 1 ;
if ( x == b[ m ] ) return m ;
int l = 1 , r = m , mid ;
while ( r - l > 1 ) {
mid = ( l + r ) >> 1 ;
if ( b[ mid ] == x ) return mid ;
if ( x < b[ mid ] ) r = mid ; else l = mid ;
}
}

const int inf = 1000000000 ;
const ll INF = ll( inf ) * ll( inf ) ;

ll dp[ maxn ][ maxn ][ maxn ] , suff[ 2 ][ maxn ] ;
bool used[ maxn ][ maxn ] ;

void dfs( int l , int r ) {
if ( used[ l ][ r ] ) return ;
used[ l ][ r ] = true ;
if ( l > r ) {
REP( i , 0 , n ) dp[ l ][ r ][ i ] = 0 ; return ;
}
if ( l == r ) {
REP( i , 0 , n ) dp[ l ][ r ][ i ] = t[ l ].u + ( i != w[ l ] ) * k ;
return ;
}
REP( i , l , r ) dfs( l , i - 1 ) , dfs( i + 1 , r ) ;
REP( i , 0 , n ) dp[ l ][ r ][ i ] = INF ;
REP( i , l , r ) {
suff[ 0 ][ n + 1 ] = suff[ 1 ][ n + 1 ] = INF ;
DOWN( j , n , 0 ) {
suff[ 0 ][ j ] = min( suff[ 0 ][ j + 1 ] , dp[ l ][ i - 1 ][ j ] ) ;
suff[ 1 ][ j ] = min( suff[ 1 ][ j + 1 ] , dp[ i + 1 ][ r ][ j ] ) ;
dp[ l ][ r ][ j ] = min( dp[ l ][ r ][ j ] , suff[ 0 ][ j ] + suff[ 1 ][ j ] + ll( k ) * ll( j != w[ i ] ) ) ;
}
}
REP( i , 0 , n ) dp[ l ][ r ][ i ] += ll( sum[ r ] - sum[ l - 1 ] ) ;
}

int main( ) {
scanf( "%d%d" , &n , &k ) ;
rep( i , n ) scanf( "%d" , &t[ i ].d ) ;
rep( i , n ) {
scanf( "%d" , &t[ i ].v ) ; a[ i ] = t[ i ].v ;
}
rep( i , n ) scanf( "%d" , &t[ i ].u ) ;
sort( a + 1 , a + n + 1 ) , sort( t + 1 , t + n + 1 ) ;
rep( i , n ) if ( i == 1 || a[ i ] != a[ i - 1 ] ) b[ ++ m ] = a[ i ] ;
sum[ 0 ] = 0 ;
rep( i , n ) {
sum[ i ] = sum[ i - 1 ] + t[ i ].u ; w[ i ] = getp( t[ i ].v ) ;
}
memset( used , false , sizeof( used ) ) ;
dfs( 1 , n ) ;
ll ans = INF ;
REP( i , 0 , n ) ans = min( ans , dp[ 1 ][ n ][ i ] ) ;
printf( "%lld\n" , ans ) ;
return 0 ;
}