Problem#
有 Alice 和 Bob 比賽射箭，每個人有 numArrows 支箭 ，一人各射 12 局，規則是: 如果第 $i$ 局的分數比另一個人大，$A_i \ge B_i$ 則 A 得到 $i$ 分。
今天 Alice 先射完了，他的結果是 [aliceArrows_0, aliceArrows_11] ，問你 Bob 的結果長怎樣，他的得分才會是最大的
想法#
這題有兩種做法: 爆搜和 DP。
之所以可以爆搜是因為局數 只有 12 局，所以能在 $\mathcal{O}(2^12)$ 內做完，bitwise 枚舉也是一樣。DP 則是把箭數當重量、得分當價值的話，問題就變成了 0/1 背包 $\mathcal{O}(nm), n=\text{12}, m=10^5$
AC Code#
backtracking#
bitwise 枚舉#
0/1 背包#
賞析#
- top-down DP作法，跟 bottom-up 邏輯差不多，差在 access 要用 function ，dp 表格不是先建好，而是在 recursive 中建立
https://leetcode-cn.com/problems/maximum-points-in-an-archery-competition/solution/cer-jin-zhi-mei-ju-by-liu-xiang-3-8q3b/
https://leetcode.com/problems/maximum-points-in-an-archery-competition/discuss/1865563/C%2B%2B-or-Backtracking-or-List-of-problems