Building Shops

Time Limit: 2000/1000 MS(Java/Others)    Memory Limit: 131072/131072 K(Java/Others) Total Submission(s): 0    Accepted Submission(s): 0

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 candyshops in thesen classrooms. The total cost consists of two parts. Building a candy shop at classroom i would have some costci . For every classroomP without any candy shop, then the distance betweenP and the rightmost classroom with a candy shop onP 's left side would be included in the cost too. Obviously, if there isa classroom without any candy shop, there must be a candy shop on its leftside. 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 severaltest 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 integersxi,ci(−109≤xi,ci≤109) , denoting the coordinate of thei -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 asingle 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

题意：给出一条直线上的若干点以及在该店建造商店的花费，求最小费用。最小费用由两部分组成，一部分是建造商店的花费（你可以选择每个点是否建造商店，不过要求没有建造商店每个点其左侧必须至少有一商店，显然，最靠左的点上必须建造商店），还有一部分是没有建造商店的点与其左侧最近商店的距离

思路：显然，这是一道动态规划的题目，但如果你只是每次单纯考虑当前点是否建造，那么这个动态规划就错了（本质已经变成了贪心），举个例子： 1 （1）， 3（5），100（1000），101（10000），102（10000），103（10000）…200（10000），显然，如果贪心过去第三个点肯定不取，但事实上，应该建造第一个点和第三个点。所以我们在考虑当前点时，用该重新考虑前面的建造情况

法一：

#include <bits/stdc++.h> using namespace std; #define mst(a,b) memset((a),(b),sizeof(a)) #define f(i,a,b) for(int i=(a);i<=(b);++i) #define ll long long const int maxn = 3005; const int mod = 1e9+7; const int INF = 0x3f3f3f3f; const double eps = 1e-6; #define rush() int T;scanf("%d",&T);while(T--) struct node { ll x,y; }a[maxn]; ll dp[maxn]; bool cmp(const node &a,const node &b) //比node a 更好的写法 {     return a.x<b.x; } int main() { int n; while(~scanf("%d",&n)) { for(int i=1; i<=n; i++) { scanf("%I64d%I64d",&a[i].x,&a[i].y); } sort(a+1,a+n+1，cmp); //使点按照坐标从左往右排序 dp[0]=0; for(int i=1; i<=n; i++) { dp[i]=INF; ll tot=0; for(int j=i; j>0; j--) { tot+=a[j].x; ll cost =a[j].y; //在j处建造商店 ll dis=tot-(i-j+1)*a[j].x; //j右侧所有点与j的距离和 dp[i]=min(dp[i],dp[j-1]+dis+cost); } } printf("%I64d\n",dp[n]); } return 0; }

法二：

状态转移方程：

   dp[i]=min(dp[i],sum[i]-sum[j]-(i-j)*(a[j].x-a[1].x)+dp[j-1]+a[j].y)；

   其中sum[i]=a[i].x-a[1].x+sum[i-1];

#include <bits/stdc++.h> using namespace std; #define mst(a,b) memset((a),(b),sizeof(a)) #define f(i,a,b) for(int i=(a);i<(b);++i) typedef long long ll; const int maxn = 100005; const int mod = 475; const ll INF = 0x3f3f3f3f; const double eps = 1e-6; #define rush() int T;scanf("%d",&T);while(T--) int n; ll dp[maxn],sum[maxn]; struct node { ll x,y; }a[maxn]; bool cmp(const node &a,const node &b) { return a.x<b.x; } int main() { while(~scanf("%d",&n)) { mst(sum,0); for(int i=1;i<=n;i++) scanf("%I64d%I64d",&a[i].x,&a[i].y); sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++) { sum[i]=a[i].x-a[1].x+sum[i-1]; dp[i]=INF; } dp[1]=a[1].y; for(int i=2;i<=n;i++) for(int j=1;j<=i;j++) { dp[i]=min(dp[i],sum[i]-sum[j]-(i-j)*(a[j].x-a[1].x)+dp[j-1]+a[j].y); } printf("%I64d\n",dp[n]); } return 0; }