題目連結:https://www.luogu.com.cn/problem/P5299
有\(2n\)張牌，
\(n\)張強化牌，每張上有一個正整數\(x(x>1)\)，如果使用後之後的每一張攻擊牌傷害都會乘上\(x\)。
\(n\)張攻擊牌，每張上有一個正整數\(x\)，使用後造成\(x\)點傷害。
随機抽上來\(m\)張，然後按照最優政策打出\(k\)張的情況下，求所有情況造成的傷害和。
\(1\leq k\leq m\leq 2n\leq 3000\)
考慮一個最優政策是啥，顯然地我們有強化牌肯定優先打出，直到打完或者隻剩最後一費。
因為翻倍至少多一倍的傷害，而我們攻擊牌肯定是從大往小選，是以不可能一張攻擊牌使得傷害翻倍。
先把兩種牌按照數組從大到小排序
我們可以分為兩種情況讨論
打出\(k-1\)張強化牌和一張攻擊牌
打出\(<k-1\)張強化牌和若幹張攻擊牌
第一種情況我們設\(f_i\)表示選出了\(i\)張強化牌的所有方案中前\(k\)張牌乘積的和。
然後枚舉一個在\(k-1\sim m\)之間的數字\(i\)表示抽到了\(i\)張強化牌，然後再枚舉攻擊力最大的一張攻擊牌，剩下的方案用組合數計算即可。
第二種情況比較麻煩，同樣的設\(f_{0,i}\)表示抽了\(i(i<k)\)張強化牌的所有方案中所有牌的乘積和。然後設\(f_{i,j}\)表示總共選了\(i\)張攻擊牌和強化牌，打出了前\(k\)張強化牌和攻擊牌時所有強化牌乘積的和，\(g_{i,j}\)則表示造成的傷害和。
然後轉移即可。
時間複雜度：\(O(nm)\)