Codevs 1025 选菜

标题叙述 Description

       在小松宿舍楼下的面前,有PK大学最精确的一个商旅——The Farmer’s Canteen(NM酒店卡塔尔。由于该食堂的菜都很准确,价格也公道,所以重重人都爱好来这边吃饭。The Farmer’s Canteen的点菜情势就像在杂货铺自行选购商品相符,人们从二个钦赐的街头进去,再从三个点名的路口出来并给付。由于来这里吃饭的总人口相当多,所以大家自觉地在步入口的时候就排成叁个长队,沿着长长的摆放着五花八门佳肴美馔的桌子举办选菜。

       小松发掘,这种选菜方式意味着,他不可能在选菜的时候离开部队去拿一些她曾经看过了的菜还是还没看过的菜,因为插入是不礼貌的,也是被BS的。

       每一种菜有二个价值,而小松也要好给种种菜定了贰个在他看来的美味价值,举例红烧小金条在小松看来是可口价值异常高的,而青花菜在小松眼里则是美味价值比非常的低的菜肴。而有点菜是果胶价值非常高的菜(比方米饭卡塔 尔(英语:State of Qatar),所以不论是它的可口价值是多少,小松都会选拔1份。以后小松带了X元钱来食堂就餐,他想掌握,在不欠帐的图景下,他选菜的可口价值总合最大是有一点点。

输入描述 Input Description

       请从输入文件farmer.in中读入相关数据。输入的第意气风发行李包裹涵七个个整数n(1≤n≤100),k(0≤k≤实在菜的档案的次序卡塔 尔(英语:State of Qatar)和叁个实数X(02020欧洲杯官方投注-2020欧洲杯官方投注网址,≤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

#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; 
}

 

本文由2020欧洲杯官方投注-2020欧洲杯官方投注网址发布于win7,转载请注明出处:Codevs 1025 选菜

相关阅读