【HDU】3516 Tree Construction

时间:2021-12-28 00:41:20

http://acm.hdu.edu.cn/showproblem.php?pid=3516

题意:平面n个点且满足xi<xj, yi>yj, i<j。xi,yi均为整数。求一棵树边只能向上和向右延展的经过所有点的最小长度。(n<=1000, 0<=xi, yi<=10000)

#include <cstdio>
using namespace std;
const int N=1005, oo=~0u>>1;
int d[N][N], x[N], y[N], n, s[N][N];
int main() {
while(~scanf("%d", &n)) {
for(int i=1; i<=n; ++i) scanf("%d%d", &x[i], &y[i]);
for(int i=1; i<n; ++i) d[i][i+1]=y[i]-y[i+1]+x[i+1]-x[i], s[i][i+1]=i+1;
for(int len=3; len<=n; ++len)
for(int i=1; i<=n-len+1; ++i) {
int j=i+len-1, l=s[i][j-1], r=s[i+1][j], &now=d[i][j], &pos=s[i][j];
now=oo;
for(int k=l; k<=r; ++k) {
int t=d[i][k-1]+d[k][j]+y[k-1]-y[j]+x[k]-x[i];
if(now>=t) {
now=t;
pos=k;
}
}
}
printf("%d\n", d[1][n]);
}
return 0;
}

  

一开始乱想= =乱搞无果= =b,于是妈呀看了题解 = =

妈呀我没想到.....d(i, j)表示i~j个点的最小代价,由于点都满足题目所给的条件,对于两棵i~k-1, k~j的树连接起来显然代价为y[k-1]-y[j]+x[k]-x[i]

设$w(i, j, k)=y[k-1]-y[j]+x[k]-x[i]$,那么得到:

$$d(i, j)=min \{ d(i, k-1)+d(k, j)+w(i, j, k) \}, i<j$$

我一开始看到$w$是三元的= =便又手推了一下四边形不等式的证明= =发现这竟然和$k$无关!即如果四边形不等式满足$w(i, j, k)+w(i', j', k) \le w(i', j, k)+w(i, j', k)$,那么和原来的一模一样!原因在哪?因为我是一个sb= =关于$w$的不等式左右加上两个$y[k-1]+x[k]$是可以约掉的我还傻x的重新证明了一下!

那么本题直接把状态变为$w(i, j)$先不管$k$了= =

我们先来证明$w$的区间单调性,很显然吧...题目已经满足= =

然后来证明$w$的四边形不等式....首先我们要一个容易证明不等式成立的式子= =

首先四边形不等式变形为

$$w(i, j')-w(i, j) \ge w(i', j')-w(i', j)$$

发现当$j$不变时(即固定),那么我们只需要判断$w(i, j')-w(i, j)$的$i$如果增大值是变大还是变小即可,如果是变小(递减)显然满足四边形不等式(因为$i' \ge i$)。

所以得到一个定理:如果$w(i, j)$满足四边形不等式,则我们只需要判断:当j不变时,$w(i, j+1)-w(i, j)$是否单调递减即可。(j同理,咦j要不要一起证啊?)

那么本题由于$w(i, j+1)-w(i, j) = y[j]-y[j+1]$与$i$无关所以满足条件...

那么水题啦= =

【HDU】3516 Tree Construction的更多相关文章

  1. 【HDU】4888 Redraw Beautiful Drawings 网络流【推断解是否唯一】

    传送门:pid=4888">[HDU]4888 Redraw Beautiful Drawings 题目分析: 比赛的时候看出是个网络流,可是没有敲出来.各种反面样例推倒自己(究其原因 ...

  2. 【BZOJ】2631&colon; tree LCT

    [题意]给定n个点的树,每个点初始权值为1,m次操作:1.x到y的点加值,2.断一条边并连一条边,保证仍是树,3.x到y的点乘值,4.x到y的点权值和取模.n,m<=10^5. [算法]Link ...

  3. 【BZOJ2212】&lbrack;Poi2011&rsqb;Tree Rotations 线段树合并

    [BZOJ2212][Poi2011]Tree Rotations Description Byteasar the gardener is growing a rare tree called Ro ...

  4. 【题解】Digit Tree

    [题解]Digit Tree CodeForces - 716E 呵呵以为是数据结构题然后是淀粉质还行... 题目就是给你一颗有边权的树,问你有多少路径,把路径上的数字顺次写出来,是\(m\)的倍数. ...

  5. 【题解】&lbrack;P4178 Tree&rsqb;

    [题解]P4178 Tree 一道点分治模板好题 不知道是不是我见到的题目太少了,为什么这种题目都是暴力开值域的桶QAQ?? 问点对,考虑点分治吧.直接用值域树状数组开下来,统计的时候直接往树状数组里 ...

  6. 【总结】Link-Cut Tree

    这是一篇关于LCT的总结 加删边的好朋友--Link Cut Tree Link-Cut Tree,LCT的全称 可以说是从树剖引出的问题 树剖可以解决静态的修改或查询树的链上信息:那如果图会不断改变 ...

  7. 【HDU】6110 路径交&lpar;2017百度之星&rpar; 线段树&plus;RMQ-LCA&plus;树链的交

    [题目]2017"百度之星"程序设计大赛 - 初赛(A) [题意]给定n个点的带边权树,m条编号1~m的路径,Q次询问编号区间[L,R]所有链的交集的长度.n<=500000 ...

  8. HDOJ 3516 Tree Construction

    四边形优化DP Tree Construction Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Jav ...

  9. 【HDU】2191 多重背包问题

    原题目:悼念512汶川大地震遇难同胞——珍惜现在,感恩生活 [算法]多重背包(有限背包) 动态规划 [题解]http://blog.csdn.net/acdreamers/article/detail ...

随机推荐

  1. Swift 2&period;2发布

    Swift 2.2 发布了.支持linux平台.Swift是一种使用现代的安全设计方式和软件设计模式构建的通用编程语言.该版本语言更新如下: SE-0001: Allow (most) keyword ...

  2. linux——基本配置

    环境:Ubuntu 12.04.2 LTS (GNU/Linux 3.5.0-23-generic i686) 网络配置 #临时改变 #修改IP和子网掩码 sudo ifconfig eth0 192 ...

  3. SCC(强连通分量)

    1.定义: 在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(SC---strongly connected). 有向图中的极大强连通子图,成为强连通分量(SCC---strongly ...

  4. LINUX下的MYSQL默认表名区分大小写

    让MYSQL不区分表名大小写的方法其实很简单: 1.用ROOT登录,修改/etc/my.cnf,该文件的路径也可能是/usr/my.cnf. 2.加入一行:lower_case_table_names ...

  5. GroupLayout 布局

    文档说明: 以下引自:Java™ PlatformStandard Ed. 7 public class GroupLayout extends Object implements LayoutMan ...

  6. DbUtility-第一次接触

    DbUtility这个以前就知道,可是由于底层是4.5的框架,我就一直没有仔细看过,最近自己的开发框架升级到了4.5,就开始学习这个组件. 总体来说,这个组件用起来非常简单.举例说明: await d ...

  7. 积累的VC编程小技巧之框架窗口及其他

    1.修改主窗口风格 AppWizard生成的应用程序框架的主窗口具有缺省的窗口风格,比如在窗口标题条中自动添加文档名.窗口是叠加型的.可改变窗口大小等.要修改窗口的缺省风格,需要重载CWnd::Pre ...

  8. &lbrack;Swift&rsqb;LeetCode606&period; 根据二叉树创建字符串 &vert; Construct String from Binary Tree

    You need to construct a string consists of parenthesis and integers from a binary tree with the preo ...

  9. Web前端JQuery面试题(二)

    Web前端JQuery面试题(二) 1.请写出jquery的语法? <script type="text/javascript"> $(document).ready( ...

  10. 7&period;01-beautiful&lowbar;soup2

    # pip install beautifulsoup4 from bs4 import BeautifulSoup html_doc = """ <html&gt ...