HDU - 6024 Building Shops(女生赛)

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
碎念念,早就想写dp的题了,上次就因为dp不会,影响我拿奖呜呜呜呜,我的报名费呀

dp【i】【j】为到第i个教室，前一个糖果店的位置是j，的最小费用是多少。
分两种，一是在这里修建糖果店。dp【i】【i】=min（dp【i】【i】，dp【i-1】【j】+v【i】）（1<=j<i）。
二是不修建糖果店。dp【i】【j】=min（dp【i】【j】，dp【i-1】【j】+d【i】-d【j】）（1<=j<i）。
当然，第一个教室必须修建糖果店 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;
}