当前位置:网站首页>HDU - 6024 Building Shops(女生赛)
HDU - 6024 Building Shops(女生赛)
2022-07-06 09:25:00 【是小张张呀 zsy】
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;
}
边栏推荐
猜你喜欢
ucore lab5
LeetCode#237. Delete nodes in the linked list
力扣刷题记录
C4D quick start tutorial - creating models
JS --- detailed explanation of JS DOM (IV)
Take you to use wxpy to create your own chat robot (plus wechat interface basic data visualization)
C语言数组的概念
Unpleasant error typeerror: cannot perform 'ROR_‘ with a dtyped [float64] array and scalar of type [bool]
Leetcode notes - dynamic planning -day6
How to do agile testing in automated testing?
随机推荐
China's earthwork equipment market trend report, technical dynamic innovation and market forecast
UCORE lab5 user process management experiment report
Unpleasant error typeerror: cannot perform 'ROR_‘ with a dtyped [float64] array and scalar of type [bool]
ucore lab7
Stm32 dossiers d'apprentissage: saisie des applications
csapp shell lab
ArrayList set
LeetCode#2062. Count vowel substrings in strings
Learning record: USART serial communication
学习记录:TIM—基本定时器
Research Report on market supply and demand and strategy of China's Medical Automation Industry
Learning record: Tim - Basic timer
Market trend report, technological innovation and market forecast of pneumonia drugs obtained by Chinese hospitals
Market trend report, technical innovation and market forecast of lip care products in China and Indonesia
Leetcode notes - dynamic planning -day6
0 - 1 problème de sac à dos (1)
Winter vacation daily question - maximum number of balloons
What are the software testing methods? Show you something different
STM32学习记录:输入捕获应用
Accounting regulations and professional ethics [4]