|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
int n, k, sum;
|
|
|
int c[101]; //价钱
|
|
|
int num[101]; //
|
|
|
int m[101]; //美味价值
|
|
|
int f[1001], number, bi;
|
|
|
bool b[101]; //b数组是由来确定他是否为已处理过的必选菜。
|
|
|
|
|
|
//01背包问题，注意两个小问题就好了:
|
|
|
// 1.把价格和money都扩大十倍。
|
|
|
// 2.同一物品会出现两次，然并卵。所幸题目提示了，用种类哈希数组映射到vis上去就好了，如果是必选物品i就设置vis[i]为0。
|
|
|
int main() {
|
|
|
//输入+输出重定向
|
|
|
freopen("../1300.txt", "r", stdin);
|
|
|
|
|
|
//b数组是由来确定他是否为已处理过的必选菜。
|
|
|
memset(b, false, sizeof(b));
|
|
|
|
|
|
//有n个菜式，有k种菜是必选的，小松带来了X元钱（精确到“角”）。
|
|
|
double x;
|
|
|
scanf("%d%d%lf", &n, &k, &x);
|
|
|
|
|
|
int tot = (int) (x * 10);//为了方便处理，在这里我们把价钱全部乘10。
|
|
|
//表示菜桌上从入口到出口的所有菜的价格
|
|
|
//由于价钱是精确到角的,所以这里*10不影响该题的答案
|
|
|
double a;
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
scanf("%lf", &a);
|
|
|
c[i] = (int) (a * 10);
|
|
|
}
|
|
|
|
|
|
//表示菜桌上从入口到出口的所有菜的美味价值
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
scanf("%d", &m[i]);
|
|
|
|
|
|
//表示菜桌上从入口到出口的所有菜的种类编号
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
scanf("%d", &number);
|
|
|
num[number] = i;//编号相同的菜后来的会覆盖掉前面的，这样接下来处理就简单了
|
|
|
} //在这个地方我们把输入的数当成下标，存放下标的位置，就很容易寻找它对应的价值和美味值..
|
|
|
|
|
|
for (int i = 1; i <= k; i++) {
|
|
|
scanf("%d", &bi);//读入种类
|
|
|
tot -= c[num[bi]]; //根据种类，换算出价格
|
|
|
sum += m[num[bi]]; //根据种类，换算出美味值
|
|
|
b[bi] = true; //注意：在这个时候b[]内是bi;
|
|
|
}
|
|
|
//tot就是上限的价格，也可以理解为就是背包的上限容量
|
|
|
//sum就是最终的美味值和，目前只是必选菜的美味值和
|
|
|
|
|
|
//01背包
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
if (!b[i]) //如果不是必选菜，才能进行01背包处理
|
|
|
for (int j = tot; j >= c[num[i]]; j--) {
|
|
|
f[j] = max(f[j], f[j - c[num[i]]] + m[num[i]]);//01背包求解
|
|
|
}
|
|
|
|
|
|
//输出结果
|
|
|
printf("%d", f[tot] + sum);
|
|
|
//关闭文件
|
|
|
fclose(stdin);
|
|
|
return 0;
|
|
|
}
|
