一些男生女生（一共至少2人）坐成一圈做游戏。游戏做n轮，每轮从任意一个人那里开始，顺时针或逆时针数若干个人（不超过100个），把他们的性别分别记下来，于是每一轮游戏都得到一个B\G序列（B for boy G for girl）。给出n轮游戏的B\G序列，求可能的最少参与游戏人数。
例如，两轮的结果分别是BGGGBBBGG、BBGGG，那么最少可能有6个人：GGGBBB。
n<=16
方便起见，称一轮游戏的结果为一个串。如果某个串是另一个串的子串，那么这个串是没用的，预处理时丢弃掉。然后这个问题就好像是把这若干个串首尾相“粘”，拼成一个尽可能短的圈。
首尾相"粘"
关于这种构思的正确性，我们假定得到了最优解的环形序列，然后随意指定某个位置为起始位置0，编号顺时针逐位增加。那么每个串都是这个最优解的一部分，或者若干圈再加上一部分。接着按照起始编号从小到大给所有的串排序，由于预处理去掉了所有被包含的子串，所以不存在两个串起始编号相同的情况。规定每个串贡献的部分是它的起始位置到下一个串的起始位置之前，那么各个串的贡献无交集并且和为最优解。故而所有可能的最优解都可以用上图的形式表示，只需枚举所有这些可能的情况然后挑出其中绿色部分的和最大的一个，则灰色部分最小。
只有一个串的情况
另外需要注意只有一个串的情况，这时候相当于它自己的尾巴和自己的头重合了，一个串可以和自身完全重合，但绿色的部分应是除了这种情况以外的最大重叠部分。
程序实现上，先随意指定某个串作为起点，记为串0。
定义dp[s][i][t]为：当串的集合为s，正\反向串i作为终点时，圈中重叠部分和的最大值（t=0\1，正\反向）。注意s一定包含串0，并且串i和串0的重叠部分也要算在dp内（首尾相接）。决策是倒数第二个位置是s中的哪个串。
于是有转移方程:
dp[s][i][t] = max{dp[s-i][x][t']+rep[x,t'][i,t]-rep[x,t'][0,0]+rep[i,t][0,0]}
其中rep是两个各自有特定方向的串最大重叠部分，另外我们规定串0总是正向的。
网友评论