太原市制作网站,wordpress面包屑文字大小如何调整,企业品牌vi设计,建网站的公司哪家好1025 选菜 时间限制: 1 s空间限制: 128000 KB题目等级 : 黄金 Gold题解题目描述 Description在小松宿舍楼下的不远处#xff0c;有PK大学最不错的一个食堂——The Farmer’s Canteen#xff08;NM食堂#xff09;。由于该食堂的菜都很不错#xff0c;价格也公道#xff0c… 1025 选菜 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题解 题目描述 Description 在小松宿舍楼下的不远处有PK大学最不错的一个食堂——The Farmer’s CanteenNM食堂。由于该食堂的菜都很不错价格也公道所以很多人都喜欢来这边吃饭。The Farmer’s Canteen的点菜方式如同在超市自选商品一样人们从一个指定的路口进去再从一个指定的路口出来并付款。由于来这里就餐的人数比较多所以人们自觉地在进入口的时候就排成一个长队沿着长长的摆放着各式各样佳肴的桌子进行选菜。 小松发现这种选菜方式意味着他不能在选菜的时候离开队伍去拿一些他已经看过了的菜或者没有看过的菜因为插队是不礼貌的也是被BS的。 每个菜有一个价值而小松也自己给每个菜定了一个在他看来的美味价值例如红烧小黄鱼在小松看来是美味价值很高的而花菜在小松眼里则是美味价值极低的菜肴。而有一些菜是营养价值极其高的菜例如米饭所以无论它的美味价值是多少小松都会选择1份。现在小松带了X元钱来食堂就餐他想知道在不欠帐的情况下他选菜的美味价值总合最大是多少。 输入描述 Input Description 请从输入文件farmer.in中读入相关数据。输入的第一行包括两个个整数n1≤n≤100k0≤k≤实际菜的种类和一个实数X0≤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 样例输出 Sample Output 10 /*把价格*2变成整数01背包
*/
#includeiostream
#includecstdio
#includealgorithm
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.idy.id;}
int main(){scanf(%d%d%lf,n,k,s);ms*10/1;for(int i1;in;i){scanf(%lf,s);a[i].ws*10/1;}for(int i1;in;i)scanf(%d,a[i].v);for(int i1;in;i)scanf(%d,a[i].id);int x;for(int i1;ik;i){scanf(%d,x);vis[x]1;}for(int i1;in;i){if(vis[a[i].id]1){vis[a[i].id]2;ansa[i].v;m-a[i].w;}}for(int i1;in;i){if(vis[a[i].id])continue;for(int jm;ja[i].w;j--){dp[j]max(dp[j],dp[j-a[i].w]a[i].v);}vis[a[i].id]1;}ansdp[m];printf(%d,ans);
} 转载于:https://www.cnblogs.com/thmyl/p/7222879.html
