hiho一下第242周《手势识别》题目分析

1
0

《手势识别》题目分析

本题是一道非常复杂+繁琐的搜索+DP题目。

模式图一共有N幅,所以模式图的集合一共有2^N种。对于任一模式图集合S,S能拼成最终识别验证图的充要条件是:

1) S中的模式图叠加起来与最终识别验证图完全重合

2) S中的模式图能以某种顺序首尾相连连起来

对于问题1:

无论是模式图还是最终识别验证图,都可以看成是16个点的无向图,本质上最多有120条不同的边。我们可以用bitset来表示一个模式图或最终识别验证图。假设bitset上的基本运算是O(1)的,那么求出2^N种模式图集合的叠加结果总时间复杂度是O(2^N)的。

对于问题2:

由于前一幅模式图的终点是后一幅模式图的起点,故我们可以通过dp对集合S进行判断。假设state是集合的二进制编码,令f[i][state]为当前处于第i幅模式图且合法连接模式图集合为state是否可行,通过枚举下一幅图j进行转移。总时间复杂度O(N^2*2^N)

最后,本题在实现时还要特别注意处理题目中提示的地方:

“注意对输入数据中经过其他顶点的线段进行处理,如(1,1)-(4,4)与(1,1)-(2,2)-(3,3)-(4,4)依然是重合的。”

3 answer(s)

0

第二行到第N+1行,每一行的第一个坐标点一定是起点吗,即可能是终点吗?

0

(1,1)-(4,4)与(1,1)-(2,2)-(3,3)-(4,4) 是重合的, (1,1)-(4,4)与(1,1)-(3,3)-(2,2)-(4,4) 是重合的吗?

0

asd

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


转发分享