HDU - 6024 building shops (girls' competition)

C - Building Shops

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 ii 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 nn lines, each line contains two integers xi,ci(1e-9<=xi,ci<=1e9), denoting the coordinate of the ii-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

3
1 2
2 3
3 4
4
1 7
3 1
5 10
6 1

Sample Output

5
11
Broken thoughts , I wanted to write about dp That's it , Last time because dp Can't , It affects me to win the prize, woo woo , My registration fee

dp【i】【j】 For the first time i A classroom , The location of the previous candy store is j, What is the minimum cost of .
There are two kinds , One is to build a candy store here .dp【i】【i】=min（dp【i】【i】,dp【i-1】【j】+v【i】）（1<=j<i）.
Second, do not build candy stores .dp【i】【j】=min（dp【i】【j】,dp【i-1】【j】+d【i】-d【j】）（1<=j<i）.
Of course , The first classroom must build a candy store dp[1][1]=a[1].n.

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int const N=1e5+10;
typedef long long ll;
struct node{
    
   ll m,n;
}a[3010];
ll dp[3010][3010];
ll const inf=1e9+10;
int cmp(node x,node y)
{
    
    return x.m<y.m;
}
int main()
{
    
    int nn;
    while(~scanf("%d",&nn))
    {
    
        for(int i=1;i<=nn;i++)
        {
    
            scanf("%lld%lld",&a[i].m,&a[i].n);
        }
        sort(a+1,a+nn+1,cmp);
    memset(dp,inf,sizeof(dp));
        dp[1][1]=a[1].n;
        for(int i=1;i<=nn;i++)
            for(int j=1;j<i;j++)
        {
    
            dp[i][j]=min(dp[i][j],dp[i-1][j]+a[i].m-a[j].m);
            dp[i][i]=min(dp[i][i],dp[i-1][j]+a[i].n);
        }
        ll sum=inf;
        for(int i=1;i<=nn;i++)
            sum=min(sum,dp[nn][i]);
        printf("%lld\n",sum);
    }
    return 0;
}