首页 > 代码库 > zoj 2501 - A Mini Locomotive

zoj 2501 - A Mini Locomotive

题目:有一串数,从里面取出m个不同的区间,每个区间长度不能超过M,使得所取所有数字和最大。

分析:dp,单调队列,区间最大字段和。因为数据都是正的不需要单调队列维护(否则要使用)

            区间最大字段和,求出每个元素作为结束标志的前k项和;取结束位置作为dp状态;

            然后,利用单调队列维护区间长度,O(1)时间查找满足长度的最小的前j项和,做差即可。

            状态:设f(i,j)为前j个数字,取i个区间最大和;s(j)为前j个数字的最大单区间字段和;

            转移:f(i,j)= max(f(i-1,k)+ s(j)) { 其中k ≤ j-M }。

            (如果数据可以为负,方程不变,用单调队列计算单区间最大字段和即可)

说明:数据都是正的,可以用更简单的方程dp。。。(2011-11-02 00:16)

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int F[ 4 ][ 50005 ];
    int T,N,M,t,i,m,l,r,s;
    while ( ~scanf("%d",&T) )
    for ( t = 1 ; t <= T ; ++ t ) {
        scanf("%d",&N);
        for ( i = 1 ; i <= N ; ++ i )
            scanf("%d",&F[ 0 ][ i ]);
        scanf("%d",&M);
        
        for ( s = 0,l = i = 1 ; i <= N ; ++ i ) {
            s += F[ 0 ][ i ]; 
            if ( i-l >= M ) s -= F[ 0 ][ l ++ ];
            F[ 1 ][ i ] = s;
        }
        
        for ( m = 2 ; m <= 3 ; ++ m )
        for ( s = 0,i = 1 ; i <= N ; ++ i ) {
            if ( s < F[ m-1 ][ i-M ] ) 
                s = F[ m-1 ][ i-M ];
            F[ m ][ i ] = s + F[ 1 ][ i ];
        }

        int max = 0;
        for ( i = 1 ; i <= N ; ++ i )
            if ( max < F[ 3 ][ i ] )
                max = F[ 3 ][ i ];
                
        printf("%d\n",max);    
    }
    return 0;
}


zoj 2501 - A Mini Locomotive