POJ OD425. 田忌赛马
原题链接
简单
作者:
YrMrYu
,
2024-03-13 15:29:21
,
所有人可见
,
阅读 12
a = list(map(int,input().split()))
b = list(map(int,input().split()))
n = len(a)
maxBiggerCount = 0
ans = 0
def dfs(level, used, biggerCount):
global maxBiggerCount, ans
if level >= n:
if biggerCount > maxBiggerCount:
maxBiggerCount = biggerCount
ans = 1
elif biggerCount == maxBiggerCount:
ans += 1
for i in range(n):
if used[i]:
continue
# 树层去重
if i > 0 and a[i] == a[i-1] and not used[i-1]:
continue
used[i] = True
# biggerCount记录当前全排列中a[level] > b[level]的位置数量,此时a[level] == a[i]
dfs(level+1,used,biggerCount + (1 if a[i]>b[level] else 0))
used[i] = False
a.sort()
dfs(0,[False]*n,0)
print(ans)