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(1n3000), denoting the number of the classrooms.
In the following n lines, each line contains two integers xi,ci(?109xi,ci109), 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
- Source
2017 中国大学生程序设计竞赛 - 女生专场
题意:
有 n 个教室, 现在想在这 n 个教室中建一些超市, 问你最少费用为多少?
费用分为两种:
1: 在第 i 个教室建超市, 费用因为 ci
2: 没有建超市的教室的费用为它和它左边最接近的超市的坐标之间的距离
- #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[3005];
- bool cmp(node x,node y)
- {
- return x.x<y.x;
- }
- ll dp[3005];
- //dp[i] 表示只考虑前 i 个教室 的最优解
- ll dp2[3005];
- //dp2[i] 表示 第 i 个固定条件下, 前 i 个的最优解
- ll s[3005];
- int main()
- {
- int n;
- while(~scanf("%d",&n))
- {
- for(int i=1;i<=n;i++)
- {
- scanf("%lld %lld",&a[i].x,&a[i].c);
- }
- sort(a+1,a+n+1,cmp);
- memset(dp,inf,sizeof(dp));
- memset(dp2,inf,sizeof(dp2));
- memset(s,0,sizeof(s));
- dp[0]=0;
- dp[1]=dp2[1]=a[1].c;
- int pp=a[1].x;
- for(int i=1;i<=n;i++)
- {
- a[i].x-=pp;
- s[i]=a[i].x+s[i-1];
- }
- for(int i=1;i<=n;i++)
- {
- dp2[i]=dp[i-1]+a[i].c;
- // 第 i 个固定条件下, 前 i 个的最优解
- for(int j=1;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 0;
- }
- Building Shops
- Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
- Total Submission(s): 2728 Accepted Submission(s): 936
- 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(1n3000)
, 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
- Source
2017 中国大学生程序设计竞赛 - 女生专场 http://acm.hdu.edu.cn/search.php?field=problem&key=2017%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%B3%CC%D0%F2%C9%E8%BC%C6%BE%BA%C8%FC+-+%C5%AE%C9%FA%D7%A8%B3%A1&source=1&searchmode=source
Recommend
jiangzijing2015 | We have carefully selected several similar problems for you: http://acm.hdu.edu.cn/showproblem.php?pid=6286 http://acm.hdu.edu.cn/showproblem.php?pid=6285 http://acm.hdu.edu.cn/showproblem.php?pid=6284 http://acm.hdu.edu.cn/showproblem.php?pid=6283 http://acm.hdu.edu.cn/showproblem.php?pid=6282
来源: http://www.bubuko.com/infodetail-2612745.html