#include <iostream>

#include<cstring>

#include<string>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<deque>

#define ll long long

#define inf 0x3f3f3f3f

using namespace std;

struct node

{

    ll x;

    ll c;

}a[];

bool cmp(node x,node y)

{

    return x.x<y.x;

}

ll dp[];

//dp[i]表示只考虑前i个教室 的最优解

ll dp2[];

//dp2[i]表示 第i个固定条件下，前i个的最优解

ll s[];

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        for(int i=;i<=n;i++)

        {

            scanf("%lld %lld",&a[i].x,&a[i].c);

        }

        sort(a+,a+n+,cmp);

        memset(dp,inf,sizeof(dp));

        memset(dp2,inf,sizeof(dp2));

        memset(s,,sizeof(s));

        dp[]=;

        dp[]=dp2[]=a[].c;

        int pp=a[].x;

        for(int i=;i<=n;i++)

        {

            a[i].x-=pp;

            s[i]=a[i].x+s[i-];

        }

        for(int i=;i<=n;i++)

        {

            dp2[i]=dp[i-]+a[i].c;

            //第i个固定条件下，前i个的最优解

            for(int j=;j<=i;j++)

            {

                dp[i]=min(dp[i],dp2[j]+s[i]-s[j]-(i-j)*a[j].x);

            }

        }

        printf("%lld\n",dp[n]);

    }

    return ;

}

Problem Description

HDU’s n

classrooms are on a line ,which can be considered as a number line. Each
classroom has a coordinate. Now Little Q wants to build several candy shops in
these n

classrooms.

The total cost consists of two parts. Building a candy shop
at classroom i

would have some cost ci

. For every classroom P

without any candy shop, then the distance between P

and the rightmost classroom with a candy shop on P

's left side would be included in the cost too. Obviously, if there is a
classroom without any candy shop, there must be a candy shop on its left
side.

Now Little Q wants to know how to build the candy shops with the
minimal cost. Please write a program to help him.

 

Input

The input contains several test cases, no more than 10
test cases.
In each test case, the first line contains an integer n(1≤n≤3000)

, denoting the number of the classrooms.
In the following n

lines, each line contains two integers xi,ci(−109≤xi,ci≤109)

, denoting the coordinate of the i

-th classroom and the cost of building a candy shop in it.
There are no two
classrooms having same coordinate.

 

Output

For each test case, print a single line containing an
integer, denoting the minimal cost.

 

Sample Input

 

Sample Output

 

Source

 

Recommend

jiangzijing2015   |   We have carefully selected
several similar problems for you:  6286 6285 6284 6283 6282