sicily 10359 Valuable Jewellery

2023-12-12 14:59

文章标签 sicily valuable 10359 jewellery

本文主要是介绍sicily 10359 Valuable Jewellery，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

贪心

题意:
背包问题,n个物品,有重量有价值.不同的是,有k个背包,每个背包有重量上限,且最多只能放一个物品.问最大价值

数据范围:
n,k<=300000,重量,价值<=10^6,背包上限<=10^8

思路:

每个背包最多只能放一个物品,那这题一下子就水了

贪心,背包用一个map存放,物品按价值递减排序.扫描每个物品,每次在map里找这个物品的质量的下界,有的话就更新答案,维护map,无的就只能放弃了

总结:贪心,优先选择物品价值高的

这篇关于sicily 10359 Valuable Jewellery的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

http://www.chinasem.cn/article/485019。 23002807@qq.com

sicily 分类

原文出处：http://linguifan2010.blog.163.com/blog/static/1315127442010102131322482/ *************************程序设计题************************* *************************数据结构************************* sicily

uva 10359 Tiling

原题： In how many ways can you tile a 2 × n rectangle by 2 × 1 or 2 × 2 tiles?Here is a sample tiling of a 2 × 17 rectangle. Input Input is a sequence of lines, each line containing an integer numb

sicily 1225. 电子眼

/图其实是一个树加了一条边，我们找到这个环，然后枚举其中一条边的两端，看是在哪里安装电子眼。剩下的就是普通的树形dp了。。 #include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; const int MAXN = 101000; vector<

sicily 4425Easy Sort

进行一次翻转之后，接下的翻转肯定只交换相邻的数，统计逆序对。用树状数组做，新序列保存在arr中，没读入一个arr[i],就在c[arr[i]]位置加1，这时候arr[i]与之前输入的i个数中构成逆序的就是i-sum(arr[i])拉。。 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm

sicily 4876. PLAĆE 每周一赛二

树形结构转线性结构，先dfs，得到每一个结点的开始和结束访问时间s，t 记录一个数组A[1...t] 那么更新一个结点的就是A[s]+=v,A[t]-=v 采用树状数组做，OMlog2*N复杂度 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector>

sicily 1876. Basic Graph Problem 线段树+并查集+路径压缩

线段树或者RMQ都可以做，虽然是不是动态变化的，但是用线段树做也不错，，而且最近才开始弄线段树，当练练手。。。一定要路径压缩的并查集，，不然线性的话，耗时过高。。。而且不能写递归的路径压缩，我猜得。。。因为n<=100000，一般20000就会栈爆的，，，， #include<iostream> #include<cstdio> #include<cstring> using

Sicily 1099 Packing Passengers

Constraints Time Limit: 1 secs, Memory Limit: 32 MB Description PTA, Pack ‘em Tight Airlines is attempting the seemingly impossible—to fly with only full planes and still make a profit. Their strategy

Arpa's weak amphitheater and Mehrdad's valuable Hoses

背包问题？！+并查集一组朋友之中最多只能有一个人去，所以需要在写0-1背包时需要调整for循环的顺序错解： for(int i=1;i<=n;i++){sum_b=0,sum_w=0;if(pre[i]==i){for(int j=0;j<vn[i].size();j++){sum_b+=bn[vn[i][j]];sum_w+=wn[vn[i][j]];for(int k=w;k>=

Sicily Shortest path in unweighted graph

Source: http://soj.sysu.edu.cn/show_problem.php?pid=1003&cid=2104 Description 输入一个无向图，指定一个顶点s开始bfs遍历，求出s到图中每个点的最短距离。如果不存在s到t的路径，则记s到t的距离为-1。 Sample Input 输入的第一行包含两个整数n和m，n是图的顶点数，m是边数。1<=n<=1000

Sicily Connect components in undirected graph

Source: http://soj.sysu.edu.cn/show_problem.php?pid=1002&cid=2104 Description 输入一个简单无向图，求出图中连通块的数目。 Sample Input 输入的第一行包含两个整数n和m，n是图的顶点数，m是边数。1<=n<=1000，0<=m<=10000。以下m行，每行是一个数对v y，表示存在边(v,y)。顶

sicily 10359 Valuable Jewellery

相关文章