hihoCoder太阁最新面经算法竞赛4题解

0
0

Problem 1

需要注意使用的判定条件必须是充分必要条件。
比如1)边数等于点数减1 并且 2)所有点连通。

Problem 2

经典动态规划题目。
假设f(s[1..n])表示把长度为n的字符串s改写成回文串需要的操作。
如果s[1] == s[n],那么f(s[1..n]) = f(s[2..n-1])。
否则f(s[1..n])是以下三种情况的最小值:
1. 在s[n]后添加一个字符匹配s[1],f(s[1..n]) = 1 + f(s[2..n])。
2. 在s[1]前添加一个字符匹配s[n], f(s[1..n]) = 1 + f(s[1..n-1])。
3. 把s[1]和s[n]其中一个修改为另外一个使其匹配,f(s[1..n]) = 1 + f(s[2..n-1])。

Problem 3

递归求解。可以参考wikipedia上的方法: https://en.wikipedia.org/wiki/Hilbert_curve

write answer 切换为英文 切换为中文


转发分享