问题 G: 体检

问题 G: 体检

时间限制: 1 Sec  内存限制: 128 MB
提交: 272  解决: 44
[状态] [讨论版] [提交] [命题人:]
题目描述
VX玩了这么多游戏以后,感觉自己身体素质和智商都有所下降,所以决定去医院体检一下。
已知VX一共需要体检N项,并且每项体检需要时间一定的时间,并且每个项目体检时间还会随之增加。
请帮忙找出最优的体检顺序,并输出体检完所有项目的最短的总时长
输入
多实例
第一行读入T,表示共有T组数据(T=100)
  接下来共有T行,每行一个整数N,表示体检的项目数(1<=N<=6)
    接下里会有N行,每行两个数字(a,b)
    a表示体检该项目共需a分钟
    b表示当VX不在该项目时,该项目的体检时间每1分钟增加b分钟
输出
对于每组测试数据,输出一个整数,表示最短的总体检时间(保证最终答案在int范围内)
样例输入 Copy
3
1
1 2
5
1 2
2 3
3 4
4 5
5 6
2
5 5
11 10
样例输出 Copy
1
1419
66
提示
对于第二组测试数据,最优解法为:
1.先做第一项,该项耗时 1 分钟,总累计耗时1分钟
2.做第二项,该项耗时 2+3*1=5 分钟,总累计耗时6分钟
3.做第三项,该项耗时 3+4*6=27 分钟,总累计耗时33分钟
4.做第四项,该项耗时 4+5*33=169 分钟,总累计耗时202分钟
5.做第五项,该项耗时 5+6*202=1217 分钟,总累计耗时1419分钟