Browse Tag

线性dp

1039 Minimum Score Triangulation of Polygon (dp)

假设您将多边形剖分为 N-2 个三角形,对于每个三角形,该三角形的值是顶点标记的乘积,三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。
返回多边形进行三角剖分后可以得到的最低分。

CodeChef STRMRG String Merging (dp)

对于字符串 S,定义函数 F(S) 为:最少可以将 S 划分为几个连续的子串,使得每个子串仅包含相同的字符。换句话说,F(S) 等于 1 加上满足 Si ≠ Si+1 的合法下标 i 的数量。
给定两个字符串 A 和 B,长度分别为 N 和 M。你需要将这两个字符串合并成一个长度为 N + M 的字符串 C。C 的每个字符要么来源于 A,要么来源于 B,且来源于 A 的字符的相对顺序应当与在 A 中一致,来源于 B 的字符亦然。
请求出 F(C) 最小可能的值。