Beyond the Void

问题简述

有一棵Treap，每个节点有一个互不相同的数据值和权值，以及一个访问频度。一个节点的访问代价为它的访问频度乘以它在树中的深度，整棵树的访问代价定义为所有节点的访问代价之和。节点的权值可以修改为任意实数，每修改一个节点的权值的代价为K。任务是修改一些节点的权值，使得整棵树的访问代价与修改代价之和最小。 Read the rest of this entry »

问题简述

有N个诗句需要被排版为若干行，顺序不能改变。一行内可以有若干个诗句，相邻诗句之间有一个空格。定义行标准长度L，每行的不协调度为|实际长度-L|^P，整首诗的不协调度就是每行不协调度之和。任务是安排一种排版方案，使得整首诗的不协调度最小。 Read the rest of this entry »

对于我来说，这道题不易想到是动态规划，即使想到了，实现也是不容易的。

首先仔细观察表格可以发现一个等价的转化。假设一对付费节点i,j的最近公共祖先为p，如果p的nA<nB，称p为A付费节点，否则 为B付费节点。对于i和p，如果i和p的节点性质相同，则需要一倍的付费，j也相同。这时候，i,j的付费可以独立考虑了。这种付费方式与原题描述是等价 的。这一步是动态规划的必要前提条件。

经过这一步的转化，问题就明了多了。问题可以被描述为，安排每个叶节点的付费方案，使每个节点到其所有祖先需要付费之和最小。考虑一个叶 节点i到每个祖先p需要付费多少，取决于i相对于p的另一棵子树中所有节点j与i的流量F[i,j]之和。定义Cost[i,k]为叶节点i到其第k个祖 先需要的付费，我们可以求出每两个叶节点i,j的最近公共祖先p，并令Cost[i,p]和Cost[j,p]的值增加F[i,j]。

定义状态DP[i,j,k]为以第i个节点为根的子树中分配j个A节点，从根节点到i的每个祖先的状态集合为k的最小费用。k可以用二进制位表示，如果一个节点nA<nB，则标记该节点状态为A付费节点。状态转移方程为

F[i,j,k] = Min{ F[i.left,a,k+this] + F[i.right,j-a,k+this] }

其中 k+this表示加上当前节点状态

对于边界状态，就是i为叶节点，计算方法就是i的所有父节点中与i状态相同的节点k的Cost[i,k]之和，如果i与原先付费方式不同，还要加上C[i]。

观察发现F[i,j,k]的取值范围都是0..2^N，如果直接这样写，对于2^10会超空间的，只能拿到80%的分，直观难以发现如何减 少状态数，实际上后两维是有浪费的。假设叶节点为第0层，根节点为第N层，那么对于第k层的节点，它能控制的叶节点的个数最多为2^k，于是j的取值范围 就是0..2^k，一共有2^k + 1种可能。它的祖先一共有N-k个，每个祖先个状态可能有两种，于是k的取值一共有2^(N-k)种可能。因此，j,k的取值一共有(2^k + 1) * (2^(N-k)) = 2^N + 2^(N-k) <=2^(N+1)个，于是我们就可以把后两维状态数压缩到2^(N+1)，这样就不会超过空间限制了。两维的具体压缩方法可以看成是两个二进制数 连接到一起。

Read the rest of this entry »

首先要求出每对点之间的最短路径(All Pairs Shortest Path,APSP)，需要记录的是path[i][j]，表示在i点时，通向j的最短路径上比i更接近j的一个点。

然后动态规划，状态 F[i][j] 表示猫在i，老鼠在j时，猫追上老鼠的步数的数学期望。Degree(i)为点i的度。

状态转移方程

F[i][j]=sigma{ F[i'][j'] / ( Degree(j) + 1 ) } + 1

最终结果

F[C][M]
Read the rest of this entry »

这是一个需要用单调队列优化的动态规划问题。根据数据规模的提示，要想过100%就不能把时间作为一个状态量表示，而以时间区间。

于是我们写出状态 F[p][i][j]表示第i个时间区间末的时刻，钢琴在(i,j)位置的最长滑行路程。状态转移方程就是

F[p][i][j] = Max { F[p-1][i'][j'] + dist((i,j),(i’,j’)) }  为在第p个时间区间内能从(i’,j’)到(i,j)的位置

这个状态转移方程的时间复杂度是O(NMT)的，只能过50％的数据，所以要优化状态转移。由于只能直线滑动，所以每次状态转移都是线性的，取一个最大值。我们可以想办法加快取最大值的速度，单调队列！

定义当前时间为该状态是第几个被计算的，假设第p个时间区间方向为1（从下向上滑），要从下向上递推，最下面的状态时间就是0，往上一格时间增加1。对于状态F[p][i][j]，如果(i,j)处没有障碍，把(F[p-1][i][j] － 当前时间)加入单调队列，然后在单调队列中取出合法最大值，再加上当前时间的值赋给F[p][i][j]。如果(i,j)处是障碍，则F[p][i][j]赋为一个无效值，然后清空单调队列。

这样经过优化的决策时间就是均摊O(1)的，所以时间复杂度为O(NMK)。

Read the rest of this entry »