Codevs 1025 选菜

难题陈述 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

样例输出 Sample Output

10

数码范围及提醒 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; 
}

 

本文由星彩网app下载发布于星彩网app下载,转载请注明出处:Codevs 1025 选菜

TAG标签: 星彩网app下载
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。