问题2785--贪心的小H

2785: 贪心的小H

时间限制: 1 Sec  内存限制: 128 MB
提交: 242  解决: 58
[状态] [讨论版] [提交] [命题人:]
题目描述
小H是一个考古学家,有一天他发现了海盗的宝藏,但是他只带了一个背包。现在摆在面前的宝物有100多件,每个宝物都有一个类型值(type)和一个珍贵程度(value)。现在要求选择若干个宝物(可以是0个)放进背包使得x * y最大,x为选择的不同type的数量,y为总的value值之和(同一种宝物value值一致,只计算一次value值) 
输入
第一行输入一个整数n表示物品的数量(1 ≤ n ≤ 200)

第二行输入n个整数type_i表示每个物品的类型(1 ≤ type_i ≤ 200)

第三行输入n个整数value_i(-100000 ≤ value_i ≤ 100000)
输出
输出一个整数
样例输入 Copy
2
1 2
4 7
样例输出 Copy
22