题解

4 条题解

  • 0
    @ 2016-03-18 07:52:52

    #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;
    }

  • 0
    @ 2014-08-30 19:06:27

    不会

  • 0
    @ 2014-07-08 11:38:45

    #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 ;
    }

  • 1

信息

ID
1821
难度
2
分类
(无)
标签
递交数
64
已通过
38
通过率
59%
被复制
2
上传者