首页 > 代码库 > zoj 3310 - Unrequited Love

zoj 3310 - Unrequited Love

题目:给你一个数字环,从里面去除不相邻的数字,使得取出的数字和最大。

分析:dp,动态规划。

            如果没有首尾相连的话,这个题目就很简单了:

            动态方程:F(n)= max(F[ n-1 ],F[ n-2 ] + D[ n ]);

            现在告诉我们首尾相连,为了无后效性,我们要把环拆开。;

            我们把第一个元素分为两种状况,取或不取:

            当取第一个元素时,我们DP到n-1位置;当不取第一个元素时,我们DP到n位置;

            时间复杂性:O(n)。

说明:(2011-09-19 09:26)。

#include <stdio.h>
#include <string.h>

int D[ 1000002 ];
int F[ 1000002 ];
int G[ 1000002 ];

int main()
{
    int n;
    while ( ~scanf("%d",&n) ) {
        for ( int i = 1 ; i <= n ; ++ i )
            scanf("%d",&D[ i ]);
        
        /* 当选择第一个数字时 */
        memset( F, 0, sizeof( F ) );
        F[ 1 ] = D[ 1 ];
        for ( int i = 2 ; i <= n ; ++ i ) {
            F[ i ] = F[ i-2 ] + D[ i ];
            if ( F[ i ] < F[ i-1 ] )
                F[ i ] = F[ i-1 ];
        }
        
        int Max = F[ n-1 ];
        
        /* 当不选择第一个数字时 */ 
        memset( G, 0, sizeof( F ) );
        for ( int i = 2 ; i <= n ; ++ i ) {
            G[ i ] = G[ i-2 ] + D[ i ];
            if ( G[ i ] < G[ i-1 ] )
                G[ i ] = G[ i-1 ];
        }
        
        if ( Max < G[ n ] )
            Max = G[ n ];
        
        printf("%d\n",Max);
    }
    return 0;
}

zoj 3310 - Unrequited Love