问题4504--建站（数据校正）4504: 建站（数据校正）
时间限制: 1 Sec 内存限制: 512 MB
提交: 0 解决: 0
[提交] [状态] [讨论版] [命题人:]题目描述
艾利斯顿商学院的N个教室都排在一条直线上，可以看成是一个数轴。每间教室都有一个坐标。现在校长想在N个教室里的若干个建立糖果站，在每个教室建立糖果站都要一定的费用。如果一个教室没有建立糖果站，那从这个教室向左走，遇到的第一个建立糖果站的教室所走过的距离作为费用。显然，如果某个教室没有建立糖果站，那么它的左边必须有建立糖果站的教室。现在校长想知道，如何建立糖果站，总费用最小.
输入
第一行一个整数N，代表教室数目。
接下来N行，每行两个整数Xi,Ci，代表第i个教室的坐标，以及在它建立糖果站的费用。
没有两个教室坐标相同。
输出
输出一行一个整数，代表最小费用。
样例输入
【样例1】
3
1 2
2 3
3 4
【样例2】
4
1 7
3 1
5 10
6 1
【样例3】
3
1 1
9 9
10 10
样例输出
【样例1】
5
样例1说明：1处建，代价是2，然后2处走到1处代价为1，3处走到1处代价为2，代价一共为5.
【样例2】
11
样例2说明：1处建，代价是7，3处建，代价是1，5处走到3处，代价是2，6处建，代价是1，代价一共是11.
【样例3】
11
样例3说明：1处建，代价是1，2处建，低价是9，3处走到2处，代价是1，总代价是11.
来源/分类
[提交] [状态]