现在的位置: 首页 > 综合 > 正文

中世纪剑客

2017年12月23日 ⁄ 综合 ⁄ 共 601字 ⁄ 字号 评论关闭

大意为:有n个人站成一个圈,依次抽签,抽到的人与他的右手人决斗,负者出圈,剩余的人继续,两人的比赛结果即实力由一张图决定,如果A->B有边,则表示A跟B决斗则A胜利,反之亦然。但注意实力并无传递性,即A->B,B->C并不能推出A与C决斗就是A胜利,还要看A,C的边的情况。所以最后胜出的人是谁取决于决斗的次序。

现在请计算这n个人中可能胜出的人数和方案。

 

利用动态规划吧,设 f [i ,j ] = true 表示  i ~ j 范围内决斗 第j个人是否能胜利, 而设 g [i, j ] = true 表示 i ~ j 范围内决斗 第i个人是否能胜利, win[i ,j ] =true 表示i,j决斗i胜利;

那么我们最后要求的是 所有k  , 满足  f [1 ,k] =true & g[k, n] =true, 即第k个人能在前一半和后一半都胜利。

现在我们在求递推式:

1. f [i ,j] =true 的条件是 在 i ~ j-1 这些人里,存在一个可能的胜者 k ,但k要输给j, 即 存在k , f[i ,k] = true & g[k,j-1] & win[j, k] = true;

2.g[i, j] = true的条件是 在    i+1 ~ j 这些人里,存在一个可能的胜者 k,但k 要输给i, 即 存在 k,  g[ i+1,k]=true & f [k,j] = true & win[i,k ] = true;

3.一个人的时候  f[i, i] = g [i ,i ]  = true;

4.注意为了处理圈,我们将其复制一份在末尾即可。

 

 

这个算法复杂度是  O (n3)的。

抱歉!评论已关闭.