数据结构基础

【题目描述】超市（supermarket）POJ 1456

一个超市有一个待售商品集合Prod，集合中每一个商品都有一个最晚销售时间，每一个产品都需要一个单独的单位时间销售（即两件商品不能同时销售），一个销售计划是一个有序子集Sell，Sell≤Prod，根据子集中的顺序，每一个商品都能在规定时间前销售出去。一个销售计划的利润则为Sell中的所有商品的利润和。

比如，如果Prod＝{a，b，c，d}，(p_a，d_a)＝(50，2)，(p_b，d_b)＝(10，1)，(p_c，d_c)＝(20，2)， (p_d，d_d)＝(30，1)，其中pi表示商品i的价值，di表示商品i的最晚销售时间。比如一个销售计划Sell＝{d，a}，d在0开始1时刻结束销售，a在1开始2时刻结束销售，所有商品都在规定时间前完成了销售，其利润为80，其他销售计划如表8.1所示。

 

表8.1

计划表	利润
{a}	50
{b}	10
{c}	20
{d}	30
{b，a}	60
{a，c}	70
{c，a}	70
{b，c}	30
{d，a}	80
{d，c}	50

 

写一个程序，来计算一个Prod的最大利润销售计划是多少利润。

【输入格式】

一组数据以一个整数n（0≤n≤10 000）开始，接下来有n对p_i，d_i（1≤p_i≤10 000，1≤d_i≤10 000），数与数之间有空格隔开。

【输出格式】

每组数据一行，输出最大利润是多少。

【输入样例】

4 

50 2 

10 1  

20 2  

30 1

 

7 

20 1  

2 1  

10 3 

100 2  

8 2

5 20 

50 10

【输出样例】

80

185