拉格朗日插值
通过 \(n+1\) 个点 \((x_1,y_1),(x_2,y_2),\dots,(x_{n+1},y_{n+1})\) 唯一确定一个 \(n\) 次多项式。
考虑构造 \(n+1\) 个式子,对于第 \(i\) 个式子满足当 \(x=x_i\) 时值为 \(y_i\),当 \(x\not=x_i\) 时值为 \(0\),将这 \(n+1\) 个式子加起来就可以得到这个 \(n\) 次多项式。
也就是说我们有 \(f(x)=a\cdot \prod_{i\not=j}(x-x_j)\),然后过 \((x_i,y_i)\),于是 \(a=\frac{y_i}{\prod_{i\not=j}(x_i-x_j)}\),所以 \(f(x)=y_i\cdot\prod_{i\not=j}\frac{x-x_j}{x_i-x_j}\)。
给定 \(x\) 求 \(f(x)\),时间复杂度 \(O(n^2)\)。当 \(x_i\) 连续时可以预处理出前缀积、后缀积、阶乘来 \(O(n)\) 计算。
CF995F Cowmpany Cowmpensation
*动态规划,dp 优化
题目大意:
树形结构,给每个节点分配工资(值域在 \([1, d]\)),子节点不能超过父亲节点的工资,问有多少种分配方案。
数据范围 \(1\le n\le 3000,1\le d\le 10^9\)。
思路:
先列出朴素的 dp,设 \(f_{u,i}\) 表示在节点 \(x\) 的工资为 \(i\) 的方案数,我们有:
令 \(g_{u,i}\) 为 \(\sum_{j=1}^{i}f_{u,j}\) 可以把 dp 优化到 \(O(nd)\),但是 \(d\) 很大,无法通过。
但是,可以发现,\(g_{u,i}\) 是一个不超过 \(siz_{u}\) 次的多项式,证明如下:
- 当 \(u\) 是叶子时,\(g_{u,i}=i\) 是一个 \(1\) 次式。
- 有 \(g_{u,i}-g_{u,i-1}=\prod_{v\in son_u}g_{v,i}\),这个式子的次数是所有乘起来的式子的次数和,为 \(siz_u-1\)。所以 \(g_{u,i}\) 的次数就是 \(siz_u\)。
所以,对于每个 \(1\le i\le n+1\) 可以用 \(O(n^2)\) 把 \(g_{1,i}\) 的值求出来,然后来一边拉格朗日插值就可以求出 \(g_{1,d}\) 了。
APIO2016 划艇
*动态规划,dp 优化
题目大意:
有 \(n\) 个位置,每个位置要么不选要么在 \([a_i,b_i]\) 中选一个数,求有多少种方案能使得选出来的数是单调上升的。
数据范围 \(1\le n\le 500,1\le a_i\le b_i\le 10^9\)。
思路:
同样是列出朴素的 dp,设 \(f_{i,j}\) 表示第 \(i\) 个数选 \(j\) 的方案数,我们有:
预处理二维前缀和可以优化到 \(O(n\max(a_i,b_i))\),但 \(\max(a_i,b_i)\) 很大。
我们还是令 \(g_{i,j}=\sum_{k=1}^{j}f_{i,k}\),转移的式子变为 \(f_{i,j}=\sum_{k=0}^{i-1}g_{i,j-1}\)。将区间分割开后 \(g_{i,j}\) 同样是一个 \(i\) 次多项式,对于每段分开跑一次拉格朗日插值就可以求出答案。
UVA1106 Machine Works
*动态规划,斜率优化
思路:
先将所有机器按照 \(D_i\) 排序。
考虑 dp,设 \(f_i\) 表示当前买入第 \(i\) 台机器能的得到的最大收益,于是有:
将 \(\max\) 的括号打开,并整理可得:
将 \(f_j-G_j\times(D_j-1)\) 看成 \(y\),\(-G_j\) 看成 \(k\),可以直接用 cdq 或李超线段树来维护。
CF868F Yet Another Minimization Problem
*动态规划,决策单调性
题目大意:
给定一个序列 \(a\),要把它分成 \(k\) 个子段。每个子段的费用是其中相同元素的对数。求所有子段的费用之和的最小值。
数据范围 \(2\le n\le 10^5,2\le k\le \min(20,n)\)。
思路:
设 \(f_{i,j}\) 表示前 \(i\) 个数分成了 \(j\) 段的最小费用,于是有 \(f_{i,j}=\min_{k=1}^{i}(f_{k-1,j-1}+calc(k,i))\),其中 \(calc(k,i)\) 表示区间 \([k,i]\) 的费用。
我们发现,在 \(j\) 固定时,dp 是具有单调性的。假设 \(i\) 往右移一次,有 \(calc(k,i+1)=calc(k,i)+\sum_{p=k}^i[a_p=a_i]\)。可以发现,当 \(k\) 越往左,这个增量就越大。
也就是说,对于两个 \(f_{u,j-1}+calc(u,i)\) 和 \(f_{v,j-1}+calc(v,i)\) 其中 \(u<v\),若我们把 \(i\) 往右移一次,前一项值不变,后一项 \(calc(u,i)\) 的增量一定不小于 \(calc(v,i)\) 的增量。所以,当 \(i\) 往右移动的时候,最优决策点一定会增加。
将 \(j\) 那一维放在外面枚举,里面就可以分治来求解了。
APIO2016 烟火表演
*动态规划,slope trick
题目大意:
给定一棵有根树,边有边权。你可以随意修改边的边权,代价为修改前后边权的差的绝对值。求出最小的代价使得从根到每个叶子节点的距离相等。
数据范围 \(1\le n\le 3\cdot10^5\)。
思路:
先列出朴素的 dp 式子,设 \(f_u(i)\) 表示在节点 \(i\) 的子树内所有叶子节点的距离为 \(i\) 的最小代价。那么对于 \(u\) 的一个儿子 \(v\),设这条边的边权为 \(w\),那么:
若令 \(g_v(i)=\mid w-i\mid\) 那么贡献函数就是 \(g_v(i-j)\),可以发现 dp 转移式实际上是两个函数的 (min,+) 卷积。
又因为,\(g_v(i)\) 是下凸的绝对值函数,且叶子节点是下凸函数,所以可以归纳出 \(f_u(i)\) 也是下凸函数。
而我们要求的答案就是这个函数斜率为 \(0\) 的那一段,假设这一段是区间 \([L,R]\)。
那么每次的 (min,+) 卷积就相当于:
- 保留 \(L\) 左边的线段,并将他们上移 \(w\)。
- 插入一条斜率为 \(-1\) 的线段。
- 将区间 \([L,R]\) 右移 \(w\)。
- 大于 \(R\) 只需要保留一条斜率为 \(1\) 的射线。
每两个拐点之间斜率相差 \(1\),所以我们只需要记录下每条线段之间的拐点就可以还原这个函数。
实现可以用可并堆来维护。
其他题目
- ABC275EX Monster (slope trick)
- NOI2007 货币兑换 (斜率优化)