比赛场次 | 71 |
---|---|
比赛名称 | 20101025 |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2010-10-25 19:00:00 |
结束时间 | 2010-10-25 22:00:00 |
开放分组 | 全部用户 |
注释介绍 |
题目名称 | 整理书本 |
---|---|
输入输出 | book.in/out |
时间限制 | 1000 ms (1 s) |
内存限制 | 128 MiB |
测试点数 | 10 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
郭乾乐 | AAAAAAAAAA | 0.000 s | 0.00 MiB | 100 |
donny | AAAAAAAAAA | 0.000 s | 0.00 MiB | 100 |
maxiem | AAAAAAAAAA | 0.000 s | 0.00 MiB | 100 |
ybh | AAAAAAAAAA | 0.000 s | 0.00 MiB | 100 |
Achilles | AAAAAAAAAA | 0.000 s | 0.00 MiB | 100 |
reamb | AAAAAAAAAA | 0.000 s | 0.00 MiB | 100 |
苏轼 | AAAAAAAAAA | 0.000 s | 0.00 MiB | 100 |
wo shi 刘畅 | AAAAAAAAAA | 0.000 s | 0.00 MiB | 100 |
ZhouZn1 | AAAAAAAAAA | 0.000 s | 0.00 MiB | 100 |
belong.zmx | AAWAAAAAAA | 0.000 s | 0.00 MiB | 90 |
王者自由 | EAWWWWWWWW | 0.000 s | 0.00 MiB | 10 |
Citron酱 | AWWWWWWWWW | 0.000 s | 0.00 MiB | 10 |
.Xmz | AWWWEEEEEW | 0.000 s | 0.00 MiB | 10 |
make | AWWWWWWWWW | 0.000 s | 0.00 MiB | 10 |
【问题描述】
Ztc想把他满屋子的书整理一下。为了应付繁重的学习任务,ztc已经筋疲力尽了,于是他向你求助,请你帮他计算他最少需要花费多少力气。
书本分成若干堆,呈直线排布。每一堆的书本都有重量w和价值v。Ztc的任务是将所有书合成一堆。因为Ztc很看重书本的价值,所以他认为合并i,j两堆的书所需要的力气为w[i]-v[i]+w[j]-v[j]。合并后的书堆的重量和价值均为合并前两堆书的重量和价值的总和。也就是说,合并i.j两堆的书后,w=w[i]+w[j],v=v[i]+v[j]。小智个人不愿意走来走去,所以合并只能在相邻两堆书本间进行。书本合并前后,位置不变。如将1,2,3中的1,2进行合并,那么合并结果为3,3,再将3,3合并为6(1,2,3,6指重量)。
【输入】
输入文件book.in的第一行是一个整数n(2≤n≤400)。
第2~n+1行每行两个整数w和v(0<v<w≤1000)。
【输出】
输出文件book.out共一行,这一行只有一个整数f,表示最小力气。
【输入输出样例】
book.in
3
6 5
9 7
11 2
book.out
15
【输入输出样例解释】
先将前两堆合并,再将合并后的书堆与剩余的一堆合并。
【限制】
30%的数据满足:2≤n≤100
100%的数据满足:2≤n≤400