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 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
3
1 2
2 3
3 4
4
1 7
3 1
5 10
6 1
Sample Output
5
11
题意：给出n个地点的位置坐标xi和花费ci，对于每一个位置可以选择在花费ci建店或者花费左边离他最近的已建的位置的距离差，求最小花费
解题思路：dp，第一个点必建， dp[i][0]表示在该点不建，第一个点到第i个点的最小花费和，dp[i][1]表示该点建，第一个点到第i个点的最小花费和
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <cmath>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <functional>
using namespace std;
#define LL long long
const int INF=0x3f3f3f3f;
int n;
struct node
{
LL x,c;
}p[10004];
LL dp[10004][2];
bool cmp(node a,node b)
{
return a.x<b.x;
}
int main()
{
while(~scanf("%d",&n))
{
memset(dp,INF,sizeof dp);
memset(p,0,sizeof p);
for(int i=0;i<n;i++)
scanf("%lld%lld",&p[i].x,&p[i].c);
sort(p,p+n,cmp);
dp[0][1]=p[0].c;
for(int i=1;i<n;i++)
{
dp[i][1]=min(dp[i-1][0],dp[i-1][1])+p[i].c;
LL dis=0;
for(int j=i-1;j>=0;j--)
{
dis+=(p[j+1].x-p[j].x)*(i-j);
dp[i][0]=min(dp[i][0],dp[j][1]+dis);
}
}
printf("%lld\n",min(dp[n-1][0],dp[n-1][1]));
}
return 0;
}
