這題題目好難懂＝＝
本來看都看不懂，比賽的時候也沒寫出來
重新翻譯一下題目好了～
給定 N, L, K 代表，要拿的數量，至少要獲得幾個值，初始值
給你 N 個數，代表獲得這數字的機率
再給你 N 個數，代表獲得的數字Ai
問，得到至少 L 個，且 sum( Ai ) 加上 K 不小於零，的機率為多少？
（ N, L, K, Ai <= 200 ）
由於數字小，而且每個數字都要拿
所以可以直接用O( N^3 ) 的DP就可以了
三維的DP，分別為：拿幾個，獲得幾個，目前的數字和
http://codepad.org/V5oSOnzv
沒有留言:
張貼留言