Airbnb onsite的shut the box

airbnb最近经常出现的一个题

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

且也找不到解答

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

多谢大牛详细讲解！好复杂啊。。。。这种题怎么可能面试的时候写出来

不知道是不是和楼主知道的是一个题，之前参加的一个ACM校赛好像挺类似的。
最后求得是最大翻转box得数量

可以用状压DP+BFS求解

1. def dfs(num, next, index, state, stateDP, ansDP):
   
2.     if num == 0:
   
3.         x = 0
   
4.         for e in state:
   
5.             x |= (1 << e)
   
6.         stateDP[index].append(x)
   
7.         ansDP[index].append(len(state))
   
8.     else:
   
9.         if next > n or next > num:
   
10.             return
    
11.         state.append(next)
    
12.         dfs(num-next, next+1, index, state, stateDP, ansDP)
    
13.         state.pop()
    
14.         dfs(num, next+1,index, state, stateDP, ansDP)
    
15. 
    
16. n,m = map(int, input().split())
    
17. T = 1
    
18. while (n | m) != 0:
    
19.     nums = list(map(int, input().split()))
    
20.     #stateDP: 第i轮翻转时，所能到达第j种情况的状态
    
21.     #ansDP ：第i轮翻转时，所能到达第j种情况时，正面朝上的box
    
22.     stateDP, ansDP = [[] for _ in range(n)], [[] for _ in range(n)]
    
23.     for i in range(m):
    
24.         dfs(nums[i], 1, i, [], stateDP, ansDP)
    
25. 
    
26.     visited = [0] * (1 << (n+1))
    
27.     stack = [(0,0,0)] # (i轮游戏, state, ans)
    
28.     res = 0
    
29.     while len(stack) > 0:
    
30.         curI, curState, curAns = stack.pop(0)
    
31.         if curI == m:
    
32.             continue
    
33.         for i in range(len(stateDP[curI])):
    
34.             if (curState & stateDP[curI][i]) != 0:
    
35.                 continue
    
36.             newState = curState | stateDP[curI][i]
    
37.             if visited[newState] == 0: #如果当前box之前没有被翻开过，且新的状态未被访问
    
38.                 visited[newState] = 1
    
39.                 stack.append((curI+1,newState,curAns + ansDP[curI][i]))
    
40.                 res = max(res, curAns + ansDP[curI][i])
    
41.     print("Game {}: {}".format(T, res))
    
42.     n, m = map(int, input().split())
    
43.     T += 1

复制代码

这是General SWE的题吗？？ 感觉要理解懂都要一会

这题最近常考？？没在最近的面经里见到呀。。。