采果子（fruit.pas）

 

【描述】

萌萌今天心情不错，于是走到郊外旅游。他边走边向四周望望，发现周围有许多果树。萌萌数出了这些果树上果子的个数，并且估了估每个的价格（真是个奇怪的人(lz:我也觉得……)）。萌萌规定了一种采摘方案，就是对于第i棵树来说，它有a[i]个果子，且这棵树上的所有果子的价格为s[i]，摘取时间为c[i]。那么，当你摘了第i个树上的果子后，后面你所选择去摘的果树上的果子数必须大于第i棵树上的果子数目，说白了就是一个上升序列,而且他不可以往回走。他只有k小时，那么，在萌萌所拥有的限定时间内，他想知道，这样摘取得最大值是多少？

【输入格式】

第一行2个数：n（表示这条路上的大树数），k（总共时间）

接下来第n+1行，每行三个数：

a[i]（每棵树上的果子）,s[i]（这棵树上的所有果子的价格），c[i]（在每棵树上花费的时间）

【输出格式】

一个数，按这样方法摘取的最大值：m

【输入样例】

4 3

2 2 1

2 3 2 

1 7 1

4 6 2

【输出样例】

13

（先摘第3棵树上的，再摘第4棵树上的）

【数据范围】

N,k<=10000;a[i],s[i]<=maxint;

 

#include <stdio.h>
#include <stdlib.h>
#define MAX 10000

int getmaxValue(int input[][3], int count, int time){
    if(input == NULL ) return 0;
    int i = 0;
    int choiceCount = 1;
    //value, time, fruit count restrict
    int choice[MAX][3] = {{0,time,0}};
    int maxValue = 0;
    for(;i<count;i++){
        int t = 0;
        int tmax = choiceCount;
        for(;t<tmax;t++){
            //pick the tree[i]
            if(choice[t][2]<input[i][0] && choice[t][1] - input[i][2]>=0){
                choice[choiceCount][0] = choice[t][0]+ input[i][1];
                choice[choiceCount][1] = choice[t][1] - input[i][2];
                choice[choiceCount][2] = input[i][0];
                maxValue = choice[choiceCount][0]>maxValue?choice[choiceCount][0] : maxValue;
                choiceCount++;
            }
        }
    }
    return maxValue;
}

int main(){
    //fruit count/value/time cost
    int input[][3] = {{2,8,1},{2,3,2},{1,7,1}, {4,6,2}};
    int count = 4;
    int time = 3;
    printf("%d \n", getmaxValue(input, count, time));
}

use strict;
#tree infomation . 1st element means apples amount, 2nd means values, 3rd means time cost
my @data =
(2, 8, 1,
    2,3,2,
    1,7,1,
    4,6,2);
#tree amount
my $trees = 4;
#time restriction
my $hours = 3;

#use to store the max values picked
my $rvalues = 0;
#use to store the tree no picked
my @rtr;

#read tree values by index
sub Read{
    my $i = shift;
    #return mount, value, and cost;
    return $data[$i*3], $data[$i*3+1],$data[$i*3+2];
}

sub f{
    my ($index) = @_[3];
    for($index..$trees-1){
        my($tvalue, $trestrict, $tlhours, undef, @tresult) = @_;
        my ($amount,$value, $cost) = Read($_);
        #push the tree into result if the apple amount larger than picked trees.
        if($amount>$trestrict){
            $tvalue += $value;
            $trestrict = $amount;
            $tlhours = $tlhours - $cost;
            if($tlhours>=0){
                push(@tresult, $_);
#                print "pick apple from tree $_ \n Now the result is @tresult \n";
            }
            else{
                next;
            }
            if($tvalue >$rvalues){
                $rvalues = $tvalue;
                @rtr = @tresult;
            }
            f($tvalue,$trestrict,$tlhours, $_+1, @tresult);
        }
    }

}

my @t;
f(0,0,$hours,0,@t);

print "$rvalues: @rtr\n";