题材叙述 Description

澳门金沙国际 ,CODEVS 1025 选菜,codevs1025选菜

问题叙述 Description

       在小松宿舍楼下的前后,有PK高校最不利的一个旅舍——The Farmer’s
Canteen(NM食堂)。由于该餐馆的菜都很不错,价格也公道,所以重重人都欢乐来那边吃饭。The
Farmer’s
Canteen的点菜形式就好像在杂货店自选商品一样,人们从一个点名的街口进去,再从一个指定的街头出来并付款。由于来此地用餐的食指相比多,所以人们自觉地在进入口的时候就排成一个长队,沿着长长的摆放着各式各类佳肴的案子进行选菜。

      
小松发现,那种选菜形式表示,他不可以在选菜的时候离开部队去拿一些他一度看过了的菜依然没有看过的菜,因为插入是不礼貌的,也是被BS的。

      
每个菜有一个市值,而小松也融洽给各种菜定了一个在她看来的好吃价值,例如红烧小金条在小松看来是好吃价值很高的,而花菜在小松眼里则是可口价值极低的小菜。而有一些菜是营养价值极其高的菜(例如米饭),所以无论它的美味价值是不怎么,小松都会选用1份。现在小松带了X元钱来餐馆用餐,他想明白,在不欠帐的情形下,他选菜的爽口价值总合最大是稍微。

输入描述 Input Description

    
  请从输入文件farmer.in中读入相关数据。输入的第一行包涵多个个平头n(1≤n≤100),k(0≤k≤实际菜的体系)和一个实数X(0≤X≤100),表示有n个菜式,有k种菜是必选的,小松带来了X元钱(精确到“角”)。接下来的1行富含n个实数,表示菜桌上从进口到讲话的具有菜的价位(0价格10,单位“元”,精确到“角”);再接下来的1行包罗n个整数,表示菜桌上从进口到讲话的有着菜的水灵价值(0好吃价值100);再接下来一行包括n个整数,表示菜桌上从入口到讲话的具有菜的类型编号(1花色编号100)。最后一行蕴涵k个整数分别表示必选菜的项目编号。要注意的是,同一种编号的菜可以现身数十次,然而她们的价位和美味价值都是一律的。对于同样种菜(无论是否必选菜),小松最四只会选择1份(买两份红烧豆腐多没看头啊)。别的,必选菜的价位之和一定不当先X。

出口描述 Output Description

    
  请将结果输出到输出文件farmer.out中。输出包罗一个平头,表示小松能选到的菜的爽口价值总和最大是有些。

       注:你可以若是数据中不会产出小松带的钱不够买必买菜的处境。

 

样例输入 萨姆ple Input

7 1 5.0

4 1 3 0.9 2 0.5 0.9

7 3 5 2 5 0 2

6 3 5 2 4 1 2

2

样例输出 萨姆ple Output

10

数据范围及提醒 Data Size & Hint
澳门金沙国际 1

#include<iostream>
using namespace std;
int v[101]={0},c[101]={0},w[101]={0},f[10011]={0},n,m,k,x,mx=0,maxn=0,visi[101]={0};
double a,b;
int main()
{
    cin>>n>>m>>b;
    x=(int)(b*10);
    for(int i=1;i<=n;i++) 
        cin>>a,v[i]=(int)(a*10);
    for(int i=1;i<=n;i++) 
        cin>>w[i];
    for(int i=1;i<=n;i++)
    {
        cin>>k;
        visi[k]++;
        if(visi[k]>1) v[i]=w[i]=0;
        else c[k]=i;
    }
    for(int i=1;i<=m;i++) 
    {
         cin>>k;
        mx+=w[c[k]];
        x-=v[c[k]]; 
        w[c[k]]=v[c[k]]=0;
    }  
    for(int i=1;i<=n;i++)
        for(int j=x;j>=v[i];j--)
        {
               f[j]=max(f[j],f[j-v[i]]+w[i]);
               maxn=max(maxn,f[j]);
        } 
    cout<<maxn+mx; 
}

View Code

1025 选菜,codevs1025选菜 题目叙述
Description 在小松宿舍楼下的附近,有PK大学最科学的一个餐饮店——The
Farmer’s Canteen(NM食堂)。由…

标题叙述 Description

1025 选菜

 

 时间限制: 1
s

 空间限制: 128000
KB

 标题等级 : 黄金
Gold

题解

 

 

 

标题叙述 Description

       在小松宿舍楼下的内外,有PK大学最不利的一个酒家——The Farmer’s
Canteen(NM食堂)。由于该餐馆的菜都很科学,价格也公道,所以众两人都爱不释手来那边吃饭。The
Farmer’s
Canteen的点菜方式就像在百货公司自选商品一样,人们从一个指定的街口进去,再从一个点名的街头出来并给付。由于来此地吃饭的人数比较多,所以人们自觉地在进入口的时候就排成一个长队,沿着长长的摆放着各式种种佳肴的案子举行选菜。

      
小松发现,那种选菜形式意味着,他不能在选菜的时候离开部队去拿一些她曾经看过了的菜依旧尚未看过的菜,因为插入是不礼貌的,也是被BS的。

      
每个菜有一个价值,而小松也融洽给每个菜定了一个在他看来的水灵价值,例如红烧小金条在小松看来是好吃价值很高的,而花菜在小松眼里则是可口价值极低的菜肴。而有一些菜是营养价值极其高的菜(例如米饭),所以不管它的爽口价值是有点,小松都会选拔1份。现在小松带了X元钱来餐馆用餐,他想精晓,在不欠帐的动静下,他选菜的可口价值总合最大是有些。

Codevs 1025 选菜。输入描述 Input Description

    
  请从输入文件farmer.in中读入相关数据。输入的第一行包涵多少个个平头n(1≤n≤100),k(0≤k≤实则菜的品类)和一个实数X(0≤X≤100),表示有n个菜式,有k种菜是必选的,小松带来了X元钱(精确到“角”)。接下来的1行富含n个实数,表示菜桌上从进口到讲话的拥有菜的价格(0价格10,单位“元”,精确到“角”);再接下来的1行饱含n个整数,表示菜桌上从入口到讲话的持有菜的好吃价值(0可口价值100);再接下来一行包罗n个整数,表示菜桌上从入口到讲话的保有菜的项目编号(1项目编号100)。最终一行包蕴k个整数独家表示必选菜的品类编号。要留心的是,同一种编号的菜可以出现反复,然则她们的价钱和美味价值都是同一的。对于同样种菜(无论是否必选菜),小松最三只会挑选1份(买两份红烧豆腐多没看头啊)。别的,必选菜的价钱之和自然不当先X。

输出描述 Output Description

    
  请将结果输出到输出文件farmer.out中。输出包涵一个整数,表示小松能选到的菜的美味价值总和最大是稍稍。

       注:你可以假设数据中不会产出小松带的钱不够买必买菜的景色。

 

样例输入 Sample Input

7 1 5.0

4 1 3 0.9 2 0.5 0.9

7 3 5 2 5 0 2

6 3 5 2 4 1 2

2

样例输出 Sample Output

10

/*
    把价格*2变成整数,01背包
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
int n,m,k,dp[1010],ans;
double s;
int vis[110];
using namespace std;
struct node{
    int w,v,id;
}a[110];
int cmp(node x,node y){return x.id<y.id;}
int main(){
    scanf("%d%d%lf",&n,&k,&s);m=s*10/1;
    for(int i=1;i<=n;i++){
        scanf("%lf",&s);
        a[i].w=s*10/1;
    }
    for(int i=1;i<=n;i++)scanf("%d",&a[i].v);
    for(int i=1;i<=n;i++)scanf("%d",&a[i].id);
    int x;
    for(int i=1;i<=k;i++){
        scanf("%d",&x);
        vis[x]=1;
    }
    for(int i=1;i<=n;i++){
        if(vis[a[i].id]==1){
            vis[a[i].id]=2;
            ans+=a[i].v;
            m-=a[i].w;
        }
    }
    for(int i=1;i<=n;i++){
        if(vis[a[i].id])continue;
        for(int j=m;j>=a[i].w;j--){
            dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);
        }
        vis[a[i].id]=1;
    }
    ans+=dp[m];
    printf("%d",ans);
}

 

       在小松宿舍楼下的附近,有PK大学最正确的一个餐馆——The Farmer’s
Canteen(NM食堂)。由于该旅舍的菜都很不错,价格也公道,所以广大人都喜欢来那边吃饭。The
Farmer’s
Canteen的点菜格局就像在杂货店自选商品一律,人们从一个点名的街头进去,再从一个指定的路口出来并付款。由于来此地用餐的食指相比较多,所以人们自觉地在进入口的时候就排成一个长队,沿着长长的摆放着各式各个佳肴的桌子进行选菜。

       在小松宿舍楼下的前后,有PK大学最正确的一个餐馆——The Farmer’s
Canteen(NM食堂)。由于该餐馆的菜都很不利,价格也公道,所以广大人都喜欢来这边吃饭。The
Farmer’s
Canteen的点菜方式就像是在超市自选商品一样,人们从一个指定的路口进去,再从一个指定的街口出来并给付。由于来那里吃饭的人口比较多,所以人们自觉地在进入口的时候就排成一个长队,沿着长长的摆放着各式各类佳肴的台子举办选菜。

      
小松发现,那种选菜格局表示,他不可能在选菜的时候离开部队去拿一些他早就看过了的菜如故没有看过的菜,因为插入是不礼貌的,也是被BS的。

      
小松发现,那种选菜方式表示,他无法在选菜的时候离开部队去拿一些他现已看过了的菜照旧没有看过的菜,因为插入是不礼貌的,也是被BS的。

      
每个菜有一个价值,而小松也自己给种种菜定了一个在他看来的可口价值,例如红烧小金条在小松看来是美味价值很高的,而花菜在小松眼里则是可口价值极低的菜肴。而有一些菜是营养价值极其高的菜(例如米饭),所以随便它的可口价值是有点,小松都会挑选1份。现在小松带了X元钱来餐馆用餐,他想了然,在不欠帐的情事下,他选菜的好吃价值总合最大是多少。

      
每个菜有一个价值,而小松也要好给各样菜定了一个在他看来的可口价值,例如红烧小金条在小松看来是可口价值很高的,而花菜在小松眼里则是好吃价值极低的菜肴。而有一些菜是营养价值极其高的菜(例如米饭),所以不管它的可口价值是多少,小松都会接纳1份。现在小松带了X元钱来餐馆吃饭,他想精通,在不欠帐的场地下,他选菜的好吃价值总合最大是稍微。

输入描述 Input Description

输入描述 Input Description

    
  请从输入文件farmer.in中读入相关数据。输入的首先行包罗多个个平头n(1≤n≤100),k(0≤k≤实在菜的类型)和一个实数X(0≤X≤100),表示有n个菜式,有k种菜是必选的,小松带来了X元钱(精确到“角”)。接下来的1行涵盖n个实数,表示菜桌上从进口到讲话的兼具菜的价位(0价格10,单位“元”,精确到“角”);再接下来的1行富含n个整数,表示菜桌上从进口到讲话的具备菜的好吃价值(0好吃价值100);再接下来一行包蕴n个整数,表示菜桌上从进口到讲话的保有菜的花色编号(1项目编号100)。最终一行包涵k个整数分级表示必选菜的品类编号。要注意的是,同一种编号的菜能够现身反复,然而她们的价钱和可口价值都是同一的。对于同样种菜(无论是或不是必选菜),小松最三只会选拔1份(买两份红烧豆腐多没看头啊)。别的,必选菜的价钱之和肯定不当先X。

    
  请从输入文件farmer.in中读入相关数据。输入的率先行包含多个个平头n(1≤n≤100),k(0≤k≤实则菜的门类)和一个实数X(0≤X≤100),表示有n个菜式,有k种菜是必选的,小松带来了X元钱(精确到“角”)。接下来的1行包括n个实数,表示菜桌上从进口到讲话的有所菜的价钱(0价格10,单位“元”,精确到“角”);再接下来的1行富含n个整数,表示菜桌上从入口到讲话的享有菜的爽口价值(0可口价值100);再接下来一行包涵n个整数,表示菜桌上从进口到讲话的兼具菜的档次编号(1系列编号100)。最终一行包罗k个整数分别表示必选菜的花色编号。要留意的是,同一种编号的菜可以现身反复,不过她们的价位和可口价值都是相同的。对于同样种菜(无论是或不是必选菜),小松最五只会采用1份(买两份红烧豆腐多没看头啊)。其余,必选菜的价位之和必然不超过X。

输出描述 Output Description

出口描述 Output Description

    
  请将结果输出到输出文件farmer.out中。输出包括一个整数,表示小松能选到的菜的可口价值总和最大是稍稍。

    
  请将结果输出到输出文件farmer.out中。输出包蕴一个整数,表示小松能选到的菜的美味价值总和最大是稍稍。

       注:你可以假如数据中不会产出小松带的钱不够买必买菜的景色。

       注:你可以假若数据中不会现出小松带的钱不够买必买菜的情况。

 

 

样例输入 Sample Input

样例输入 Sample Input

7 1 5.0

7 1 5.0

4 1 3 0.9 2 0.5 0.9

4 1 3 0.9 2 0.5 0.9

7 3 5 2 5 0 2

7 3 5 2 5 0 2

6 3 5 2 4 1 2

6 3 5 2 4 1 2

2

2

样例输出 Sample Output

样例输出 萨姆ple Output

10

10

数据范围及提醒 Data Size & Hint

数码范围及提示 Data Size & Hint

#include<iostream>
using namespace std;
int v[101]={0},c[101]={0},w[101]={0},f[10011]={0},n,m,k,x,mx=0,maxn=0,visi[101]={0};
double a,b;
int main()
{
    cin>>n>>m>>b;
    x=(int)(b*10);
    for(int i=1;i<=n;i++) 
        cin>>a,v[i]=(int)(a*10);
    for(int i=1;i<=n;i++) 
        cin>>w[i];
    for(int i=1;i<=n;i++)
    {
        cin>>k;
        visi[k]++;
        if(visi[k]>1) v[i]=w[i]=0;
        else c[k]=i;
    }
    for(int i=1;i<=m;i++) 
    {
         cin>>k;
        mx+=w[c[k]];
        x-=v[c[k]]; 
        w[c[k]]=v[c[k]]=0;
    }  
    for(int i=1;i<=n;i++)
        for(int j=x;j>=v[i];j--)
        {
               f[j]=max(f[j],f[j-v[i]]+w[i]);
               maxn=max(maxn,f[j]);
        } 
    cout<<maxn+mx; 
}
#include<iostream>
using namespace std;
int v[101]={0},c[101]={0},w[101]={0},f[10011]={0},n,m,k,x,mx=0,maxn=0,visi[101]={0};
double a,b;
int main()
{
    cin>>n>>m>>b;
    x=(int)(b*10);
    for(int i=1;i<=n;i++) 
        cin>>a,v[i]=(int)(a*10);
    for(int i=1;i<=n;i++) 
        cin>>w[i];
    for(int i=1;i<=n;i++)
    {
        cin>>k;
        visi[k]++;
        if(visi[k]>1) v[i]=w[i]=0;
        else c[k]=i;
    }
    for(int i=1;i<=m;i++) 
    {
         cin>>k;
        mx+=w[c[k]];
        x-=v[c[k]]; 
        w[c[k]]=v[c[k]]=0;
    }  
    for(int i=1;i<=n;i++)
        for(int j=x;j>=v[i];j--)
        {
               f[j]=max(f[j],f[j-v[i]]+w[i]);
               maxn=max(maxn,f[j]);
        } 
    cout<<maxn+mx; 
}

 

 

相关文章