Codevs 1025 选菜

题材叙述 Description

CODEVS 1025 选菜,codevs1025选菜

亚洲必赢app官方下载 ,难题叙述 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中。输出包涵一个整数,表示小松能选到的菜的好吃价值总和最大是有点。

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

 

样例输入 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

样例输出 萨姆ple Output

10

数码范围及提醒 Data Size & Hint
亚洲必赢app官方下载 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食堂)。由…

1025 选菜

 

 时间限制: 1
s

 空间范围: 128000
KB

 题目等级 : 黄金
Gold

题解

 

 

 

题材叙述 Description

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

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

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

输入描述 Input Description

    
  请从输入文件farmer.in中读入相关数据。输入的第一行包涵八个个整数n(1Codevs 1025 选菜。≤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

样例输出 萨姆ple 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);
}

 

标题叙述 Description

       在小松宿舍楼下的左右,有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

样例输入 萨姆ple 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

样例输出 Sample 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; 
}

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图