CODEVS 1025 選菜

       在小松宿舍樓下的不遠處，有PK大學最不錯的一個食堂——The Farmer’s Canteen（NM食堂）。由於該食堂的菜都很不錯，價格也公道，所以很多人都喜歡來這邊吃飯。The Farmer’s Canteen的點菜方式如同在超市自選商品一樣，人們從一個指定的路口進去，再從一個指定的路口出來並付款。由於來這裡就餐的人數比較多，所以人們自覺地在進入口的時候就排成一個長隊，沿著長長的擺放著各式各樣佳餚的桌子進行選菜。

       小松發現，這種選菜方式意味著，他不能在選菜的時候離開隊伍去拿一些他已經看過了的菜或者沒有看過的菜，因為插隊是不禮貌的，也是被BS的。

       每個菜有一個價值，而小松也自己給每個菜定了一個在他看來的美味價值，例如紅燒小黃魚在小松看來是美味價值很高的，而花菜在小松眼裡則是美味價值極低的菜餚。而有一些菜是營養價值極其高的菜（例如米飯），所以無論它的美味價值是多少，小松都會選擇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。

       請將結果輸出到輸出文件farmer.out中。輸出包含一個整數，表示小松能選到的菜的美味價值總和最大是多少。

       註：你可以假設數據中不會出現小松帶的錢不夠買必買菜的情況。

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

10

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