首页 > 代码库 > zoj 3211 - Dream City

zoj 3211 - Dream City

题目:javaman来到了一个城市,这里有很多长着金币的树,每棵树每晚还会结出新的金币,

           现在他每天白天只能砍一棵树,最多在这里呆m天,求能得到的最大金币数。

分析:贪心+dp,二维01背包。如果砍树的集合确定,那一定按照b递增的顺序砍,因此排序后背包。

说明:(2011-11-02 05:49)。

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

#define max(a,b) ((a)>(b)?(a):(b))

typedef struct nide
{
    int bas,add;
}dnode;
dnode D[ 255 ];
int F[ 255 ][ 255 ];

int cmp( constvoid* a, constvoid* b )
{
    dnode* p = (dnode*)a;
    dnode* q = (dnode*)b;
    return p->add - q->add;
}

int main()
{
    int T,n,m,t,i,j,v;
    while ( scanf("%d",&T) != EOF ) 
    for ( t = 1 ; t <= T ; ++ t ) {
        scanf("%d%d",&n,&m);
        for ( i = 1 ; i <= n ; ++ i )
            scanf("%d",&D[ i ].bas);
        for ( i = 1 ; i <= n ; ++ i )
            scanf("%d",&D[ i ].add);
        qsort( &D[ 1 ], n, sizeof( dnode ), cmp );
        
        memset( F, 0, sizeof( F ) );
        for ( i = 1 ; i <= n ; ++ i )
        for ( j = 1 ; j <= m ; ++ j ) {
            v = (j-1)*D[ i ].add+D[ i ].bas;
            if ( F[ i ][ j ] < F[ i-1 ][ j-1 ] + v )
                F[ i ][ j ] = max( F[ i-1 ][ j ], F[ i-1 ][ j-1 ] + v );
        }
        
        printf("%d\n",F[ n ][ m ]);
    }
    return 0;
}

zoj 3211 - Dream City