● 1004 - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: huhaiming (一生只爱她), 信区: Program
标  题: 1004
发信站: 荔园晨风BBS站 (Sun May 25 10:20:35 2003), 站内信件

//旅游路线在有限的金钱下达到最大的满意度
//ZOJ Monthly, May 2003 Contest 1004
//Traveling in Solar System
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int n,m,t,cost[100],pre[100],a[5001][100];

inline int max(int a,int b){
        return a>b?a:b;
}

int main()
{
        int i,j,k;
        int testcase;
        freopen("1004.in","r",stdin);
        scanf("%d",&testcase);
        while(testcase--){
                scanf("%d%*s%d",&t,&m);
                n=0;
                for(i=0;i<m;i++){
                        scanf("%*s%d",&k);
                        for(j=0;j<k;j++){
                                scanf("%*d%*s%d%*s",&cost[n]);
                                n++;
                        }
                }
                for(i=0;i<n;i++) scanf("%d",&pre[i]);
                for(i=0;i<=t;i++) a[i][0]=0;
                for(i=1;i<=t;i++)
                        for(j=1;j<=n;j++){
                                a[i][j]=a[i][j-1];
                                if (i>=cost[j-1]) a[i][j]=max(a[i][j],
a[i-cost[j-1]][j-1]+pre[j-1]);
                        }
                k=a[t][n];
                for(i=0;i<=t;i++) if (a[i][n]==k) break;
                printf("%d %d\n",i,k);
        }
        return 0;
}

--

菩提本无树，明镜亦非台

本来无一物，何处惹尘埃

※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.0.200]

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店