hdu3516 Tree Construction
2024-10-06 19:50:34
Problem Description
Consider a two-dimensional space with a set of points (xi, yi) that satisfy xi < xj and yi > yj for all i < j. We want to have them all connected by a directed tree whose edges go toward either right (x positive) or upward (y positive). The figure below shows
an example tree.
Write a program that finds a tree connecting all given points with the shortest total length of edges.
an example tree.
Write a program that finds a tree connecting all given points with the shortest total length of edges.
Input
The input begins with a line that contains an integer n (1 <= n <= 1000), the number of points. Then n lines follow. The i-th line contains two integers xi and yi (0 <= xi, yi <= 10000), which give the coordinates of the i-th point.
Output
Print the total length of edges in a line.
Sample Input
5
1 5
2 4
3 3
4 2
5 1
1
10000 0
1 5
2 4
3 3
4 2
5 1
1
10000 0
Sample Output
12
0
0
这题要注意树的左端点必定在左上端点向下做垂线和右下端点向左作垂线的交点,思路和石子合并差不多,需要用四边形优化。
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
#define ll long long
#define inf 999999999
int x[1006],y[1006],dp[1006][1006],s[1006][1006];
int dis(int x1,int y1,int x2,int y2){
return abs(x1-x2)+abs(y1-y2);
}
int main()
{
int n,m,i,j,len,k;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++){
scanf("%d%d",&x[i],&y[i]);
dp[i][i]=0;
}
for(i=1;i<=n-1;i++){
s[i][i+1]=i;
dp[i][i+1]=dis(x[i],y[i],x[i+1],y[i+1]);
}
for(len=3;len<=n;len++){
for(i=1;i+len-1<=n;i++){
j=i+len-1;
dp[i][j]=inf;
for(k=s[i][j-1];k<=s[i+1][j];k++){
if(dp[i][j]>dp[i][k]+dp[k+1][j]+abs(y[j]-y[k])+abs(x[i]-x[k+1]) ){
dp[i][j]=dp[i][k]+dp[k+1][j]+abs(y[j]-y[k])+abs(x[i]-x[k+1]);
s[i][j]=k;
}
}
}
}
printf("%d\n",dp[1][n]);
}
return 0;
}
最新文章
- js this理解
- 使用SVN同步资源后图标样式的详细解读
- 快速入门系列--WebAPI--03框架你值得拥有
- laravel 数据库迁移
- Source Insight 使用
- Qt5 Addin 出现问题模块计算机类型“x64”与目标计算机类型“X86”冲突
- HDU 1599 find the mincost route (无向图floyd最小环详解)
- codeforces55D数位dp
- 使用vscode对c进行调试
- Beautifulsoup 和selenium 的查询
- js获取url,截取url参数,截取url后文件名
- 3、原生jdbc链接数据库之锁与事务
- [JavaScript-Function] Function Invocation/Call(函数调用) 以及call() and apply() 方法
- 从零开始学 Web 之 移动Web(三)Zepto
- 子shell以及什么时候进入子shell
- <;计算机网络>;计算机网络和应用层
- git 推送出现 ";fatal: The remote end hung up unexpectedly"; 解决方案
- logstash安装与logstash-input-jdbc插件使用
- canvas :原生javascript编写动态时钟
- 企业如何选择合适的BI工具?
热门文章
- Centos 6 下安装 OSSEC-2.8.1 (一)
- EGADS框架处理流程分析
- (十五)xml模块
- 【Linux】常用的Linux可插拔认证模块(PAM)应用举例:pam_limits.so、pam_rootok.so和pam_userdb.so模块
- kubernets之服务的实现方式
- 什么是xss攻击
- React中的合成事件
- 【高并发】ReadWriteLock怎么和缓存扯上关系了?!
- 探索微软开源Python自动化神器Playwright
- 简易双色球dome分享