You have n Pokemon, a Poke Balls, and b Ultra Balls. Pokemon i is caught with probability pi by Poke Ball, ui by Ultra Ball. You can use at most one of each ball type per Pokemon. Find the largest expected catches.
If you throw both balls at Pokemon i, the catch probability is pi+ui−pi⋅ui (at least one succeeds). The constraint is two-dimensional: exactly a Poke Balls AND exactly b Ultra Balls. Standard DP is O(n⋅a⋅b), which is O(n3). Too slow.