大意为:有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)的。