《手势识别》题目分析

本题是一道非常复杂+繁琐的搜索+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)依然是重合的。”