当前位置:网站首页>HDU - 6024 building shops (girls' competition)
HDU - 6024 building shops (girls' competition)
2022-07-06 16:03:00 【It's Xiao Zhang, 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
Broken thoughts , I wanted to write about dp That's it , Last time because dp Can't , It affects me to win the prize, woo woo , My registration fee
dp【i】【j】 For the first time i A classroom , The location of the previous candy store is j, What is the minimum cost of .
There are two kinds , One is to build a candy store here .dp【i】【i】=min(dp【i】【i】,dp【i-1】【j】+v【i】)(1<=j<i).
Second, do not build candy stores .dp【i】【j】=min(dp【i】【j】,dp【i-1】【j】+d【i】-d【j】)(1<=j<i).
Of course , The first classroom must build a candy store 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;
}
边栏推荐
- Research Report of peripheral venous catheter (pivc) industry - market status analysis and development prospect prediction
- 树莓派CSI/USB摄像头使用mjpg实现网页摄像头监控
- Analyse du format protobuf du rideau en temps réel et du rideau historique de la station B
- Shell脚本编程
- [exercise-5] (UVA 839) not so mobile (balance)
- Gartner:关于零信任网络访问最佳实践的五个建议
- C语言数组的概念
- 0 - 1 problème de sac à dos (1)
- New to redis
- X-Forwarded-For详解、如何获取到客户端IP
猜你喜欢
Analyse du format protobuf du rideau en temps réel et du rideau historique de la station B
D - Function(HDU - 6546)女生赛
Nodejs+vue网上鲜花店销售信息系统express+mysql
frida hook so层、protobuf 数据解析
Penetration test 2 --- XSS, CSRF, file upload, file inclusion, deserialization vulnerability
差分(一维,二维,三维) 蓝桥杯三体攻击
Determine the Photo Position
信息安全-威胁检测引擎-常见规则引擎底座性能比较
[teacher Gao UML software modeling foundation] collection of exercises and answers for level 20 cloud class
b站 實時彈幕和曆史彈幕 Protobuf 格式解析
随机推荐
China earth moving machinery market trend report, technical dynamic innovation and market forecast
【练习-6】(PTA)分而治之
HDU - 6024 Building Shops(女生赛)
Optimization method of path problem before dynamic planning
差分(一维,二维,三维) 蓝桥杯三体攻击
PySide6 信号、槽
Perform general operations on iptables
Opencv learning log 19 skin grinding
Auto.js入门
Penetration test (8) -- official document of burp Suite Pro
【练习-2】(Uva 712) S-Trees (S树)
Nodejs+vue网上鲜花店销售信息系统express+mysql
[exercise-9] Zombie's Treasury test
Accounting regulations and professional ethics [1]
【练习-8】(Uva 246)10-20-30==模拟
China's earthwork equipment market trend report, technical dynamic innovation and market forecast
Accounting regulations and professional ethics [3]
【练习-5】(Uva 839)Not so Mobile(天平)
Shell Scripting
信息安全-安全编排自动化与响应 (SOAR) 技术解析