济南 Day2

动态规划

最长公共子序列


$O(nlogn)$做法: 转换成最长不下降子序列

具体做法: 数组b[i]表示当前长度为i最长不下降子序列

  • 如果$c_i \ge a[len]$ 那么就可以构造更长的序列,所以$len++, \ b[len]=c[i]$
  • 否则我们就要把$c_i$插入到之前的序列当中,找到第一个大于它的并替换掉

乘积最大


区间DP

状态:$f[i][j]$表示前i个数,有j个乘号的最大乘积

转移方程:$f[i][j]=max(f[k][j-1]*num[k+1][i]), \ k<i$

需要用到高精乘

P1429 平面最近点对(加强版)

题目

题目描述
给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的

输入输出格式
输入格式:
第一行:n;2≤n≤200000

接下来n行:每行两个实数:x y,表示一个点的行坐标和列坐标,中间用一个空格隔开。

输出格式:
仅一行,一个实数,表示最短距离,精确到小数点后面4位。

输入输出样例
输入样例#1:
3 1 1
1 2
2 2
输出样例#1:
1.0000

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×