Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 262144/131072 K (Java/Others)
问题描述
Lotus有nn种字母，给出每种字母的价值以及每种字母的个数限制，她想构造一个任意长度的串。 定义串的价值为：第1位字母的价值*1+第2位字母的价值*2+第3位字母的价值*3…… 求Lotus能构造出的串的最大价值。（可以构造空串，因此答案肯定\geq 0≥0）
输入描述
第一行是数据组数T(0 \leq T \leq 1000)T(0≤T≤1000)。 对于每组数据，第一行一个整数n(1 \leq n \leq 26)n(1≤n≤26)，接下来nn行，每行2个整数val_i,cnt_i(|val_i|,cnt_i\leq 100)val?i??,cnt?i??(∣val?i??∣,cnt?i??≤100)，分别表示第ii种字母的价值和个数限制。
输出描述
对于每组数据，输出一行一个整数，表示答案。
输入样例
2 2 5 1 6 2 3 -5 3 2 1 1 1
输出样例
35 5
思路：
比赛时我的思路是把字母从小到大排序，然后排除负值字母，但是在终测时挂掉了。
原来，我少考虑了一种情况：
在某些情况下，前面加上一个负值的字母，反而会使后面的每个字母都多乘了1
这样的话，如何处理呢？
前面的字母不确定，但后面的字母一定会是大权值的，是确定的，所以我们从后往前处理，先往里填最大的，
每增加一个字母就更新一遍总和（再加一遍已添加字母的权值），直至总和不会增加为止
bestcoder#9--1001--Lotus and Characters
原文：http://www.cnblogs.com/liuzhanshan/p/6338013.html