Beyond the Void

这是一个孩子之间有分配的树形动态规划问题，一般解决的方法为左孩子右兄弟法或孩子背包分配。

左孩子右兄弟表示法中，状态设定为

F[i,j]表示以i为根的子树以及以i右边兄弟为根的子树中选j个点需要删除边的最少数量。F[i,j]还隐含了i的父亲已经被选，否则i是不可能被选的。

状态转移方程为

F[i][j] = Min
{
F[i.brother][j] + 1 (不选节点i)
F[i.child][k] + F[i.brother][j-k-1] (选节点i) 0<=k<=i子树及兄弟子树大小-1 且 k<=j-1
}

边界条件

F[i][0] = F[i.brother][0] + 1
节点0为一个虚构的节点，如果节点i没有兄弟(或儿子)，则它的兄弟(或儿子)为0。
F[0][0]=0
F[0][j]=INF (j>0，INF为一个极大的值)

目标状态

左孩子右兄弟表示法的目标状态表示不很直观，一棵子树分配P个节点，需要表示成子树根第一个孩子及其兄弟分配P-1的节点。另外，如果不是根节点，还要增加1，表示与它的父节点的边也断掉。
Ans = Min{ F[根节点的第一个孩子][P-1] , F[非根节点的第一个孩子][P-1] + 1 }

如果用孩子背包分配法，状态可以表示为

F[i][j]为以i为根的子树中选择j个节点要删除边的最少数量。

状态转移方程为

F[i][j] = Min { Sigma{ F[i.child[k]][m[k]] } } 其中 sigma[m[k]] = j-1
直接在孩子中分配不易，需要再进行一次DP，运用背包的思想，设状态

G[a][b]为对于特定的i时i的前i个孩子分配j个节点的最小值

G[a][b] = Min { G[a-1][b-k] + F[i.child[a]][k] }

于是F[i][j]可以表示为 F[i][j] = G[i.childcount][j-1]

边界条件为

对于每个节点i
G[0][0]=0
G[0][j]=INF (j>0 INF为一个极大的值)

当i为叶节点时
F[i][0]=1
F[i][1]=0

目标状态

Ans = Min{ F[根节点][P] , F[非根节点][P] + 1}

对于这道题，两种方法的时间复杂度均为O(N^3)。左孩子右兄弟法的优点在于状态转移比较简单，缺点是不够直观，尤其在表示目标状态的时候，另外边界情况的考虑也比较复杂，还有就是需要额外建树。孩子背包分配的方法优点是状态直观，易于表示，容易写成非递归，缺点是状态转移较为复杂，需要用一个背包再分配一次。我个人比较倾向于孩子背包分配法，除非必须，我一般都会写成这样的。

Read the rest of this entry »

把原序列相邻每项做差，然后问题就转化成了求一个串的最长不重叠重复子串，且两个子串相距至少一位，可以用后缀数组做。

首先求出后缀数组和Height数组，Height[i]=LCP(SA[i],SA[i-1])。接下来二分答案A，判定A是否为可行解。判断方法是找出在Height数组中找出连续的一段Height[i..j]，使得i<=k<=j均满足Height[k]>=A，并且i-1<=k1,k2<=j中，要有Max{SA[k1]} – Min{SA[k2]} >= A + 1(距离相差至少1)，这时A是可行的。

后缀数组的分组思想十分重要，这道题就是一个经典应用，还应用到了求最长公共子串(LCS)问题。
Read the rest of this entry »

这道题不同于一般的次短路径问题，因为允许边重走。看似更为复杂了，其实是更简单了一些。方法为先用Heap+Dijkstra求出1和N的单源最短路径，把无向边看成两个有向边，然后枚举每单向条边(u,v)，计算Dist=dis(1,u) + dis(N,v)，看看此时Dist的值是否大于dis(1,N)，如果是的话用它更新次短路径，保留一个最小的值。

USACO 2006 November Gold

Read the rest of this entry »

判断一个图的最小生成树是否唯一，可以求其次小生成树。如果它的次小生成树权值之和等于最小生成树权值之和，则最小生成树不唯一，否则最小生成树唯一。

求次小生成树我的方法是O(N^2 + M)的。首先求出最小生成树，记录权值之和为MinST。然后枚举添加边(u,v)，加上以后一定形成一个环，找到环上非(u,v)边的权值最大的边，把它删掉，计算当前生成树的权值之和，取所有枚举加边后生成树权值之和的最小值，就是次小生成树。

实际上具体更简单的方法为从每个顶点i，遍历整个最小生成树，定义F[j]为从i到j的路径上最大边的权值，用O(N)的方法求出每个F[j]。然后枚举顶点i的邻域，遍历每条不再最小生成树中的边(i,j)，加上这条边，并删除环上最大边(非(i,j))，新的生成树权值之和为MinST + w(i,j) – F[j]，记录其最小值即可，时间复杂度为O(N^2 + M)。求最小生成树可以用最简单的Prim，时间复杂度为O(N^2)，用更好的算法是没有意义的。

这种方法比起那种求出最小生成树后，枚举删除最小生成树上每条边，然后再求最小生成树的方法应该要快些，因为那种方法的时间复杂度为O(N * ( N * logN + M) )(Prim + Heap)。
Read the rest of this entry »

这是一个二维的LIS问题，先把第一维排序离散化，把第二维的值存到线性表A中。接下来就是求路径划分了，根据Dilworth定理，最长反链长度等于最小链划分数，所以只需求最长下降序列长度。

由于数值范围有限，可以用计数排序+基数排序，求LIS用二分查找，时间复杂度为O(NlogN)。

另外也可以直接用最小路径覆盖解决。
Read the rest of this entry »