现在的位置: 首页 > 综合 > 正文

ZOJ 1918 Ferry Loading II

2019年04月15日 ⁄ 综合 ⁄ 共 1383字 ⁄ 字号 评论关闭

设f(i,j)表示第i次运输能将第j辆车运到对岸,抵达时所花的最小时间。

f(i,j)=f(i-1,j-k)+回岸的时间T+T。当然,若回岸时车还未到达,f(i,j)=j车抵达的时间+T。

 

#include <cstdio>
#include 
<string>

#define min( x, y ) ( x < y ? x : y )
#define max( x, y ) ( x > y ? x : y )

int T, N, M, CS;
int t[1500];
int b[2][1500];    // 第n次渡过m人最小时间,滚存

void init ()
{
    scanf ( 
"%d%d%d"&N, &T, &M );
    
int i;
    
for ( i = 1; i <= M; i ++ )
        scanf ( 
"%d"&t[i] );
}


void dp ()
{
    
int i, j, k, p;
    
int minTime = 1 << 30, minStep, step;
    memset ( b, 
64sizeof ( b ) );
    
for ( j = 1, p = 0, step = 1; j <= N; j ++ )
    
{
        b[p][j] 
= T + t[j];
        
if ( j == M && b[p][j] < minTime )
            minTime 
= b[p][j], minStep = step;
    }

    
//pt ( p );
    for ( i = 2, p = 1 - p, step ++; i <= M; i ++, p = 1 - p, step ++ )
    
{
        memset ( b[p], 
64sizeof ( b[p] ) );
        
for ( j = i; j <= min ( M, i * N ); j ++ )
        
{
            
for ( k = 1; k <= N; k ++ )
                b[p][j] 
= min ( b[p][j], max ( b[1 - p][j - k] + T, t[j] ) + T );
            
if ( j == M && b[p][j] < minTime )
                minTime 
= b[p][j], minStep = step;
        }

        
//pt ( p );
    }

    printf ( 
"%d %d ", minTime, minStep );
}


int main ()
{
    
//freopen ( "in.txt", "r", stdin );
    
//freopen ( "out.txt", "w", stdout );
    scanf ( "%d"&CS );
    
int i;
    
for ( i = 0; i < CS; i ++ )
    
{
        init ();
        dp ();
    }

    
return 0;
}

抱歉!评论已关闭.